#include<bits/stdc++.h>
using namespace std;
vector<bool> v(500001);
bool check(vector<bool> v , int a){
for(int i = 1;i*i<=a/2;i++){
    if(v[a-i*i]){
        return true;
    }
}
return false;
}
string ans;
int n;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i = 1;i*i<500001;i++){
    v[i*i] = true;
}
vector<int>a(n);
for(int i = 0;i<n;i++){
    cin>>a[i];
    if(check(v , a[i])){
        ans.push_back(1 + '0');
        continue;
    }
    ans.push_back(0 + '0');
}
cout<<ans;
return 0;
}
