#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;
    unordered_map<int,int>f;
    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;
        if (f[c]==1){
            cout<<"1";
            continue;
        }
        if (f[c]==-1){
            cout<<"0";
            continue;
        }
        bool d=1;
        for (int j=0;b[j]<c&&d;j++){
            if (a[c-b[j]]==1){
                d=0;
            }
        }
        if (!d){
            f[c]=1;
            cout<<"1";
        }else{
            f[c]=-1;
            cout<<"0";
        }
    }
    return 0;
}

