你刚给你的小弟弟 Erling 买了一个有趣的拼图。这是一个 $3 \times 3$ 的棋盘，上面有八个方形棋子，你可以将棋子滑入空格中。在随机打乱棋子后，游戏的目标是将棋盘从起始状态：
通过一次滑动一个棋子的方式，恢复到以下目标状态：
玩了一会儿拼图后，Erling 声称他可以用最少的步数解决任何实例。因为你不相信他，所以你编写了一个程序来最优地解决这些拼图。
第一行输入给出一个整数 $1 \le n \le 100$，表示测试用例的数量，随后是一个空行。每个测试用例由三行组成，给出了棋盘的起始配置，每行包含三个符号，随后是一个空行。所有测试用例都包含符号 $1 \dots 8$ 和 # 各一次，其中 # 代表空格。
对于每个测试用例，输出解决该拼图所需的最少移动次数，如果无法完成，则输出 impossible。
样例
输入格式 1
2 123 4#5 786 123 456 87#
输出格式 1
2 impossible