Conway's Game of Life

John Conway was a brilliant English mathematician in the late 20th and early 21st centuries. Today is is most popularly known for his Game of Life, in which a very small set of rules allows for some complex emergent behavior. The rules of the game are thus:

• Take a grid of squares, each square able to either hold a "cell" or be empty.
• There are 8 possible squares surrounding each cell.
  • If a cell has fewer than 2 neighbors, it will die on the next turn.
  • If a cell has 2 or 3 neighbors, it will remain on the next turn.
  • If a cell has more than 3 neighbors, it will die on the next turn.
  • If a square is empty but has exactly 3 nieghbors, then a cell will appear in that square on the next turn.

Below we have a 5x5 grid of squares. Squares occupied by a cell are marked with an X. For all grids we will be considering, imagine they "wrap" from the left/right sides and the top/bottom. That is, the topmost and bottommost rows can "see" each other, as can the leftmost and rightmost columns. (In this way we could imagine the grid existing on a toroid instead of a flat plane).

Turn 0:
┌─┬─┬─┬─┬─┐
│ │X│X│X│ │
├─┼─┼─┼─┼─┤
│ │ │ │ │ │
├─┼─┼─┼─┼─┤
│ │ │X│ │ │
├─┼─┼─┼─┼─┤
│ │X│X│ │ │
├─┼─┼─┼─┼─┤
│ │ │ │X│ │
└─┴─┴─┴─┴─┘
Turn 1:
┌─┬─┬─┬─┬─┐
│ │ │X│X│ │
├─┼─┼─┼─┼─┤
│ │X│ │X│ │
├─┼─┼─┼─┼─┤
│ │X│X│ │ │
├─┼─┼─┼─┼─┤
│ │X│X│X│ │
├─┼─┼─┼─┼─┤
│ │ │ │X│ │
└─┴─┴─┴─┴─┘
Turn 2:
┌─┬─┬─┬─┬─┐
│ │ │ │X│X│
├─┼─┼─┼─┼─┤
│ │X│ │X│ │
├─┼─┼─┼─┼─┤
│X│ │ │ │ │
├─┼─┼─┼─┼─┤
│ │X│ │X│ │
├─┼─┼─┼─┼─┤
│ │X│ │ │X│
└─┴─┴─┴─┴─┘

We can see that on Turn 0 we begin with 7 cells, then on Turn 1 there are 10 cells, and finally on Turn 2 there are 9 cells. The somewhat chaotic nature of the simulation sometimes makes it difficult to predict how many cells will be present on the nth Turn, unless we perform the actual simulation to determine the answer.

Problem Statement

Input Data
First line is Q, the quantity of testcases.
Q lines then follow, each with four space-separated values W H N C, where W is the quantity of columns in the grid, H is the quantity of rows in the grid, N is the quantity of turns the simulation should be run for, and C is a binary string of digits representing the initial state of the grid. The string will be generated by taking the initial starting grid and reading the values from left-to-right in each row.

Answer
Should be Q space-separated integers, corresponding to the quantity of cells remaining after N turns of the simulation in each testcase.

Example

input data:
2
5 5 2 01110000000010001100000103
20 18 18 101000101100101011101101011110010101011100011001100010101011001100111100010110101001111110101001110001110001111110000110100111011000010010101100110111100110100110100111010001000010101001000111101001111001111110100011101111110010001111110111110010110010011000000101010100011000110010010000101111100101011001000111100001111111101011010111101001011000010111100001

answer:
9 56