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

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

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

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


    return 0;
}

