Life on a Torus

Conway's game of life is played on a torus formed of m × n square cells. An m × n torus is an m × n rectangle whose left and right edges have been glued together, as well as its top and bottom edges. Each cell is identified by its coordinates (r, c), which give the row number and column number. Every cell is either dead or alive. The state of the game is the pattern of live and dead cells on the torus.

Every cell on the torus has exactly 8 neighbors, the cells that are horizontally, vertically, and diagonally adjacent. In particular, the neighbors of cell (1, 1) are (0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), and (2, 2). The neighbors of cell (0, 1) are (m, 0), (m, 1), (m, 2), (0, 0), (0, 2), (2, 0), (2, 1), and (2, 2).

At each step in time, the state of the game changes. The state of each cell at step i + 1 is determined from the state of its 8 neighbors at step i, according to the following rules:

• If 1 or fewer of the cell's neighbors were alive at step i, then the cell is dead at step i + 1.
• If 2 of the cell's neighbors were alive at step i, then the state of the cell at step i + 1 is the same as its state at step i.
• If 3 of the cell's neighbors were alive at step i, then the cell is alive at step i + 1.
• If 4 or more of the cell's neighbors were alive at step i, then the cell is dead at step i + 1.

The initial state is called the seed of the system. For k ∈ N∗, a state of the game has period k if, when the game is at this state, it returns to exactly the same state k steps later. For instance, the configuration in the left diagram of Figure 2 has period 2: after one step we get the configuration in the right diagram, and after one more step we get the configuration in the left diagram again.

For a given seed, the period of the seed is the smallest k ∈ N∗ such that the game, starting from this seed, eventually reaches a state with period k. Given a seed, compute the period of the system.

The input consists of several test cases. The first line contains an integer giving the number of test cases. Each test case follows. The first line of a test case contains two positive integers 3 ≤ m ≤ 8 and 3 ≤ n ≤ 8 separated by a single space: m is the number of rows of the torus and n is the number of columns. The next m lines represent the seed: each line describes a row and consists of exactly n characters, each of which is 'x' for a dead cell or 'o' for a live cell.

For each test case, produce one line. This line contains a positive integer p > 0, the period of the given seed. There must be no blank lines in the output.

Figure 2: Illustration of the second test case in the sample input: a seed with period two and the configuration it leads to