#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,c;
    vector<bool>a(500000);
    vector<int>b;
    for (int i=1;i*i<=500000;i++){
        a[i*i]=1;
        b.push_back(i*i);
    }
    cin>>n;
    for (int i=0;i<n;i++){
        cin>>c;
        bool d=1;
        for (int j=0;b[j]<c&&d;j++){
            if (a[c-b[j]]==1){
                d=0;
            }
        }
        if (!d){
            cout<<"1";
        }else{
            cout<<"0";
        }
    }
    return 0;
}

