import java.util.*;

class Solution {
    public int[] solution(long[] numbers) {
        //numbers.length <= 10^4
        //numbers[0]<=10^15, 2^15 * 5^15 < 2^15 * 2^15* 2^15 * 2^15
        // 1 - 1 - 1
        // 2 - 010 - 1
        // 3 - 011 - 1
        // 4 - 100 - 0
        // 5 - 101 - 0
        // 6 - 110 - 1
        // 7 - 111 - 1
        // 8 -  0001000 - 1 FJ=3 
        // 42 - 0101010  // 64, 32^, 16, 8^, 4, 2^, 1
        // 45 - 0101101 - 
        // 63 - 0111111
        // 95 - 1011111 ㅂㄱㄴ
        // 127 - 1111111 / FJ=6
        // 128 - 000000010000000 / FJ=7
        // 255 - 000000011111111 / FJ=7
        
        
        int len=numbers.length;
        int[] answer = new int[len];
        
        
        for(int i=0;i<len;i++) {
            answer[i]=doSome(numbers[i]);
        }
        
        
        return answer;
    }
    
    public int doSome(long n) {
        StringBuilder sb=new StringBuilder();
        
        long curr=n;
        boolean firstFlag=false;
        int jisu=60;
        int firstJisu=-1;
        
        while(jisu!=-1) {

                
            if(curr/(long)Math.pow(2,jisu)==1) {
                sb.append("1");
                if(!firstFlag) {
                    firstJisu=jisu;
                }
                firstFlag=true;

                
             //   System.out.println("firstJisu "+firstJisu);
                
                curr-=Math.pow(2,jisu);
            } else if(firstFlag && curr/(long)Math.pow(2,jisu)==0) {
                sb.append("0");
            }
            
            jisu--;
        } //while
       
        int t=0;
        while(true) {
            if(Math.pow(2,t)-1<=firstJisu && firstJisu<=Math.pow(2,t+1)-2) {
                break;
            }
            t++;
        }
        //System.out.println("t "+t);
       // System.out.println("before sb.length " +sb.length());
        
        while(sb.length()<=(long)Math.pow(2,(t+1))-2) {
            sb.insert(0,"0");
        }
        
        
        
        
       // System.out.println(sb.toString());
        Character c=sb.toString().charAt(sb.toString().length()/2);
        return isSymm(sb.toString(),c);
        
        
    }
    
    public int isSymm(String str,Character origC) {
        
        
        if(str.length()==1) { //리프
            return 1;
        }
        
        if(origC=='1') {
            StringBuilder sb=new StringBuilder(str);
            int leftMid=(0+str.length()/2)/2;
            int rightMid=((str.length()/2+1)+(str.length()))/2;
            int left=isSymm(sb.substring(0,str.length()/2),sb.toString().charAt(leftMid));
            int right=isSymm(sb.substring(str.length()/2+1,str.length()),sb.toString().charAt(rightMid));
            if(left==1 && right==1) {
                return 1;
            } else {
                return 0;
            }
        } else { //부모가 0
            boolean flag=true;
            
            for(int i=0;i<str.length();i++) {
              
                if(str.charAt(i)=='1') {
                    flag=false;
                }
                
            }
            if(flag) {
                return 1;
            } else {
                return 0;
            }
        } //부모가 0
        

        
        
    } //isSymm
}