#include <iostream>
#include <cstring>
using namespace std;
int arr[500000];
int masiv[500000];
char niz[500000];

int main() {
    int n, br = 0, i = -1;
    bool b = true;
    cin>>n;

    for(int j = 0; j < n; j++){
        br = 0;
        b = true;
        cin>>arr[j];
        do{
            i ++;
            masiv[i] = (i + 1)*(i + 1);
            if((i + 1)* (i + 1) >= arr[j]){
                for(int p = 0; p < i - 1 && b; p++){
                    for(int o = p; o < i && b; o++){
                        if(masiv[p] + masiv[o] == arr[j]){
                            niz[j] = '1';
                            br++;
                            b = false;
                        }
                    }
                }
                if(br == 0){
                    niz[j] = '0';
                }
            }
        }while((i + 1) * (i + 1) <= arr[j] && b);
    }

    for(int i = 0; i < n; i++){
        cout<<niz[i];
    }


    return 0;
}

