#include <iostream>
#include <cstring>
using namespace std;
char niz[51];
int n,a=1,b=1,chislo,kwadrat,kwadrat1,index=-1;
int prowerka(int num){
    for(int i=0;i<chislo;i++){
            kwadrat=a*a;
            for(int j=0;j<chislo;j++){
                kwadrat1=b*b;
                if(chislo==kwadrat1+kwadrat){
                    niz[index]='1';
                    i=chislo+1;
                    j=chislo+1;
                }else if(kwadrat+kwadrat1>chislo){
                    j=chislo;
                    b++;

                }else{
                    b++;
                }
            }
            a++;
            b=1;
        }
        return 0;
}
int main(){
    cin>>n;
    for(int k=0;k<n;k++){
        cin>>chislo;
        a=1;
        b=1;
        index++;
        niz[index]='0';
        prowerka(chislo);
    }
    cout<<niz;
    return 0;
}