题目描述

:::align{center} :::

从进化基因的视角来看，基因是永生的，而我们作为人类个体的角色——生命的意义——在于延续基因。在数百年后，我们作为人类个体存在的所有痕迹、关于我们的记忆、我们所有的成就，很可能都将消失并被遗忘，唯有那些通过世代繁衍成功传递下来的基因得以留存。

当然，我们并非从基因的进化视角来体验世界，但 生命游戏 正是如此。生命游戏的宇宙是一个无限大的二维正交网格，由正方形细胞构成。每个细胞处于两种状态之一：存活或死亡。每个细胞与它的八个邻居（水平、垂直或对角线相邻的细胞）发生交互。在每个时间步中，发生以下变迁：

• 任何存活的细胞，若其存活邻居少于两个，则死亡，如同因人口过少而死。
• 任何存活的细胞，若其存活邻居为两个或三个，则存活至下一代。
• 任何存活的细胞，若其存活邻居多于三个，则死亡，如同因人口过多而死。
• 任何死亡的细胞，若其存活邻居恰好为三个，则变为存活细胞，如同通过繁殖而生。

初始模式，即第 $0$ 代，由无限网格中的一个有限 $N \times M$ 区域给出，其中 $N \le 3$，$M \le 5$。这意味着任何其他格子的状态均为死亡。

基因进化是生物生命的意义所在，既是其原因与方式，也是未来生物存在的储备。游戏中的三位一体生命要求你找出以下三个问题的答案。

• 在前 $321$ 代中（包括第 $0$ 代），哪一代的种群数量达到最大？
• 这个最大值是多少？
• 第 $321$ 代的种群数量是多少？

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 300$)，表示测试用例的个数。

每个测试用例由若干行组成。第一行包含两个正整数 $N$ 和 $M$。接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串，对应初始模式。我们用 “#” 描述一个存活的细胞，用 “.” 描述一个死亡的细胞。

输出格式

对于每个测试用例，在一行中输出三个整数 $a$、$b$ 和 $c$，其中 $a$ 表示达到最大种群数量的那一代，$b$ 是该代的种群数量，$c$ 是第 $321$ 代的种群数量。如果存在多个世代达到最大种群数量，选择最小的 $a$ 输出。

3
3 3
...
##.
.#.
3 3
.#.
...
###
3 3
...
###
...

1 4 4
10 20 12
0 3 3

提示

翻译由 DeepSeek V4 Pro 完成