Chuck's Challenge 是一款游戏，玩家需要在由各种方块组成的网格迷宫中导航。玩家可能会遇到需要使用沿途获得的钥匙才能解锁的门。你需要编写一个程序来确定到达迷宫出口所需打开的最少门数。

图例

规则

• 对角线相邻的方块不视为相邻（仅限上下左右）。
• 玩家从入口方块开始游戏。
• 玩家只能访问当前所在方块相邻的可通过方块。
• 在访问过匹配的钥匙方块（'A' 匹配 'a'，'B' 匹配 'b'，以此类推）之前，门被视为不可通过。
• 起初，不稳定的地板被视为可通过；然而，如果玩家离开一个不稳定的地板并访问任何其他类型的方块，该地板将变得不可通过。
• 当一个不稳定的地板变得不可通过时，所有与之相邻的不稳定地板也会变得不可通过。
• 迷宫的外部边缘是不可通过的墙壁。

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \leq T \leq 50$)。每个测试用例以一行包含两个整数 R C ($4 \leq R, C \leq 50$) 开始。随后是一个 $R$ 行 $C$ 列的迷宫。迷宫中仅会出现图例中给出的字符。

输出格式

每个测试用例输出一行。打印到达出口所需打开的最少门数，如果无法到达出口，则打印 "Impossible"。

样例

输入格式 1

2
8 15
+++++++++++++++
+>............+
+...a...+~+~+B+
+~+++++++~+~+.+
+~++..b..C+~+.+
+~++A++++++~+.+
+....~~~~~~c+<+
+++++++++++++++
8 6
++++++
+>.A<+
+.++++
+.+.a+
+~~..+
+~~..+
+~~..+
++++++

输出格式 1

2
Impossible