一、题目描述

2x3=6 个方格中放入 ABCDE 五个字母，右下角的那个格空着。如下图所示。

和空格子相邻的格子中的字母可以移动到空格中，比如，图中的 C 和 E 就可以移动，移动后的局面分别是：

A B

D E C

A B C

D E

为了表示方便，我们把 6 个格子中字母配置用一个串表示出来，比如上边的两种局面分别表示为：

AB*DEC

ABCD*E

题目的要求是：请编写程序，由用户输入若干表示局面的串，程序通过计算，输出是否能通过对初始状态经过若干次移动到达该状态。可以实现输出 1,否则输出 0。初始状态为：ABCDE*。

输入描述
先是一个整数 n，表示接下来有 n 行状态。

输出描述
程序输出 n 行 1 或 0。

输入输出样例
示例
输入

3
ABCDE*
ABDEC
CAEDB

输出

1
1
0

二、代码实现

如果使用二维数组来存储每个字母的坐标的话，那么移动方向也是一个二维数组，操作起来不太方便。
观察字母的排布

A B C   0