你是一个全能的存在,你创造了一个矩形的世界。事实上,你的世界是如此平淡,以至于它可以用 $$$r \times c$$$ 网格来表示。网格上的每个单元格代表一个国家。每个国家都有一个占主导地位的宗教。你们的世界里只有两种宗教。其中一种宗教被称为Beingwesomeism,他们为了行善而行善。另一种宗教被称为 Pushingittofarism,他们为了做坏事而杀人。
哦,其实你并不是真正无所不能。你只有一种力量,可以无限次使用!你的力量涉及传教团体。当某个国家的传教团体,比如说$$$a$$$,经过另一个国家$$$b$$$时,他们将$$$b$$$国家的主导宗教改为$$$a$$$国家的主导宗教。
特别是,你的力量的单次使用是这样的:
- 您选择水平 $$$1 \times x$$$ 子网格或垂直 $$$x \times 1$$$ 子网格。 $$$x$$$ 的值取决于你;
- 你选择一个方向$$$d$$$。如果您选择水平子网格,您的选择将是“北”或“南”。如果您选择垂直子网格,您的选择将是东或西;
- 您选择步骤数$$$s$$$;
- 你命令子网格中的每个国家派出一个传教士小组,该小组将向 $$$d$$$ 方向行进 $$$s$$$ 步。在每一步中,他们都将访问(并实际上改变其主要宗教)所经过的所有 $$$s$$$ 国家,如上所述。
- 参数 $$$x$$$、$$$d$$$、$$$s$$$ 的选择必须确保任何传教士团体都不会离开网格。
下图展示了您的力量的一种可能的单次使用。这里,A代表一个以Beingawesomeism为主导宗教的国家,P代表一个以Pushingittoofarism为主导宗教的国家。在这里,我们选择了 $$$1 \times 4$$$ 子网格,方向为 NORTH,并且 $$$s = 2$$$ 步长。
在很大程度上,你是一个相信自由意志的存在。然而,你真的不想再收到因你的名字而发生的谋杀案。因此,你决定利用你的力量,尝试让超凡主义成为每个国家的主导宗教。
使每个人都转变为令人敬畏主义所需的最少使用次数是多少?
有神在,没有什么是不可能的。但也许你不是神?如果不可能让卓越主义成为所有国家的主导宗教,那么你也必须承认你的死亡并如此说。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) 表示测试用例的数量。
每个测试用例的第一行包含两个空格分隔的整数 $$$r$$$ 和 $$$c$$$ 表示网格的尺寸($$$1 \le r, c \le 60$$$)。接下来的 $$$r$$$ 行每行包含 $$$c$$$ 字符,描述这些国家的主要宗教。特别是,第 $$$i$$$ 行中的第 $$$j$$$ 字符描述了行 $$$i$$$ 和列 $$$j$$$ 的单元格中该国家/地区的主要宗教,其中:
- “A”表示主导宗教是Beingwesomeism;
- “P”表示占主导地位的宗教是 Pushingittofarism。
保证网格仅包含“A”或“P”字符。保证单个文件中$$$r \cdot c$$$ 的总和最多为$$$3 \cdot 10^6$$$。
输出
对于每个测试用例,输出一行,其中包含将每个人转换为Beingawesomeism所需的最小力量使用次数,或者如果不可能这样做,则输出字符串“MORTAL”(不带引号)。
示例
输入 #1
4 7 8 AAPAAAAA PPPPAAAA PPPPAAAA APAAPPPP APAPPAPP AAAAPPAP AAAAPPAA 6 5 AAAAA AAAAA AAPAA AAPAP AAAPP AAAPP 4 4 PPPP PPPP PPPP PPPP 3 4 PPPP PAAP PPPP
输出 #1
2 1 MORTAL 4
注意
在第一个测试用例中,可以通过两种用法来完成,如下:
用法1:
用法2:
在第二个测试用例中,只需使用一次电源即可完成。
在第三个测试用例中,不可能让每个人都转变为Beingawesomeism,所以答案是“MORTAL”。