#include<iostream>


using namespace std;

int main(){
int a[707],b;
for(int i=0;i<707;i++){
    a[i]=(i+1)*(i+1);
}
cin>>b;
int r;
char m[b];
int j=0,n=0;
bool dal;
for(int i=0;i<b;i++){
    dal=true;
    cin>>r;
    m[i]='0';
    j=0;
    n=0;
    while(dal){
        if(a[n]>=r){
            dal=false;
        }else{
            if(a[n]+a[j]==r){
                m[i]='1';
                dal=false;
            }else{
                if(a[j]>=r){
                    j=0;
                    n++;
                }
            }
        }
        j++;
    }
}
cout<<m;
return 0;
}
