#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
char s[N];
bool tf[N];

void __(){
    scanf("%d",&n);
    if(tf[n]) puts("1");
    else puts("0");
}


int main(){
    int tot=(1<<15);
    for(int i=1;i<tot;i++){
        for(int j=i,cnt=1;j<tot;j+=i,cnt++){
            int u=min(i,cnt),v=max(i,cnt);
            if(u*2>=v) tf[j]=1;
        }
    }
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}