P17218 [ICPC 2017 Nanning R] The Game of Life

:::align{center}  ::: From an evolutionary gene’s-eye perspective, the genes are immortal, and our role, the meaning of life, is to perpetuate the genes. In a few centuries, all traces of our existence as human individuals, memories of us, all our accomplishments, will likely be gone and forgotten, except for genes that survive from those of us who successfully reproduced through the generations. Of course, we do not experience the world from a gene’s eye evolutionary perspective, but the Game of Life does. The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells. Each cell is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically or diagonally adjacent. At each step in time, the following transitions occur. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation. Any live cell with two or three live neighbours lives on to the next generation. Any live cell with more than three live neighbours dies, as if by overpopulation. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. The initial pattern, the $0$-th generation, is given by a finite $N \times M$ grid where $N \le 3$ and $M \le 5$ as a part of the infinite grid. That implies that the state of any other grid is dead. Genetic evolution is the meaning of biologic life, in that it is the why and how of it, as well as the stock of future biological existence. The trinity life in the game requests you to find answers of three problems. At what point in the first $321$ generations, including the $0$-th generation, will the population be at its maximum? And what is that maximum? What will the population be at the $321$-th generation?

The first line of the input contains an integer $t (1 \le t \le 300)$ specifying the number of test cases. Each case consists of several lines. The first line contains two positive integers $N$ and $M$. Each of the next $N$ lines contains a string of length $M$, corresponding the initial pattern. We use “#” to describe a cell which is alive, and use “.” to describe a cell which is dead.

For each test case, output three integers $a$, $b$ and $c$ in a line, where $a$ means the $a$-th generation, $b$ is the population at that generation, and $c$ is the population at the $321$-th generation. If there are several generations whose population meets the maximum, choose the smallest $a$ for the output.