描述

在一个游乐园中，有一条被六边形陶瓷砖覆盖的街道。这些砖块从地下通过一种特殊的方式连接，每块砖在每一秒钟内会变热或变冷，并且根据相邻砖块的状态，在下一秒钟内保持原来的状态或改变。制造这些陶瓷砖时使用了一种特殊技术，使其可以突然从冷变热或反之。

给定每块砖的初始热冷状态。根据这些信息和以下规则，可以判断在未来某一秒钟内，特定的砖块是冷还是热。砖块的热冷状态变化规则如下：

• 如果某个砖块在第 $t$ 秒是热的，它将在第 $t+1$ 秒变冷，前提是它周围正好有 $3$ 块冷砖，否则它将继续保持热状态。
• 如果某个砖块在第 $t$ 秒是冷的，它将在第 $t+1$ 秒保持冷，前提是它周围有 $2$ 或 $3$ 块冷砖，否则它将在第 $t+1$ 秒变热。

游戏开始时，参与者从街道边上的第一行的某个砖块跳上，时间从零开始重置。参与者可以在接下来的每一秒钟停留在同一个砖块上，或者在下一秒钟跳到与之相邻的砖块。跳跃时不能跳过砖块。显然，参与者只能踩到冷砖。你需要编写一个程序，帮助参与者以最短的时间跨越这条街道。

输入

输入的第一行包含一个整数 $t$ ($1 <= t <= 10$)，表示测试用例的数量，接着是每个测试用例的输入数据。每个测试用例的第一行包含两个整数：$N$ ($1 <= N <= 10$)，表示砖块的行数，和 $M$ ($1 <= M <= 10$)，表示每行的砖块数。砖块 $(i, j)$ 是第 $i$ 行第 $j$ 个砖块，从左到右计数。行数从 $1$ 到 $N$，表示参与者从街道的起始边开始。注意，对于边界上的砖块，相邻砖块的数量可能少于 $6$，而内部砖块的相邻砖块数量为 $6$。接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串，由大写字母 $'H'$ 和 $'C'$ 组成。在第 $i$ 行第 $j$ 个位置的 $'C'$ 表示砖块 $(i, j)$ 在时间 $0$ 时是冷的，$'H'$ 表示砖块在该时刻是热的。

输出

对于每个测试用例，输出一行，包含一个数字 $t$，表示参与者能够跨过街道所需的最短时间，或者输出 $"impossible"$ 表示无法跨越街道，或者输出 $"impossible"$ 如果所需的最短时间大于 $1000$。

2
2 2
CH
CC
2 2
CH
HC

2
impossible

来源

Tehran 2002 Preliminary