1382_移动字母

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

图1  初始状态

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

图2  从初始状态移动C              图3   从初始状态移动E

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

AB*DEC

ABCD*E

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

第一行是一个正整数n，接下来n行，每行表示一个状态。

输出n行结果：1或0

3
ABCDE*
AB*DEC
CAED*B

1
1
0