3
ABCDE*
AB*DEC
CAED*B

1
1
0

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
public class 移动字母 {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        LinkedList<String> list = new LinkedList<String>();
        HashSet<String> set = new HashSet<String>();
        list.add("ABCDE*");
        set.add("ABCDE*");
        int dir[] = {-3,-1,1,3};
        while(!list.isEmpty()) {
            int size = list.size();
            for (int i = 0; i <size ; i++) {
                String p = list.poll();
                int index = p.indexOf('*');
                for (int j = 0; j < 4; j++) {
                    int newindex = index+dir[j];
                    if(newindex<0||newindex>p.length()-1)
                        continue;
                    if(index%3==newindex%3||index/3==newindex/3) {
                        char[] tempchar = p.toCharArray();
                        tempchar[index] = p.charAt(newindex);
                        tempchar[newindex] = p.charAt(index);
                        String news = new String(tempchar);
                        if(!set.contains(news)) {
                            set.add(news);
                            list.add(news);
                        }
                    }
                }
            }
        }
        //System.out.println(set);
        int n = sc.nextInt();
        for(int i=0;i<n;i++) {
            String s = sc.next();
            if(set.contains(s))
                System.out.println(1);
            else
                System.out.println(0);
        }
    }
}