#include<bits/stdc++.h>
using namespace std;
string s;
long long izpolzvani[256];
vector<char>KoiSaIzpolzvani;
int main() {
cin.tie(NULL);
cout.tie(NULL);
long long n,BrNechetni=0;
cin>>n;
for(long long i=-1;i<n;i++){
        label:
        BrNechetni=0;
        for(long long j=0;j<=256;j++){
            izpolzvani[j]=0;
        }
        KoiSaIzpolzvani.clear();
    getline(cin,s);
    if(i>-1){
        for(long long j=0;j<s.size();j++){
            izpolzvani[s[j]]++;
            KoiSaIzpolzvani.push_back(s[j]);

        }
        for(long long k=0;k<KoiSaIzpolzvani.size();k++){
            if(izpolzvani[KoiSaIzpolzvani[k]]%2==0 and s.size()%2==0){

            }else{
                if(izpolzvani[KoiSaIzpolzvani[k]]%2==1 and s.size()%2==1){
                    if(BrNechetni==1){
                            cout<<0;
                        i++;
                        goto label;
                    }else{
                        BrNechetni++;
                    }

            }else{
                cout<<0;
            i++;
            goto label;
            }
            }
            if(izpolzvani[KoiSaIzpolzvani[k]]%2==1 and s.size()%2==1){
                    if(BrNechetni==1){
                        i++;
                        goto label;
                    }else{
                        BrNechetni++;
                    }

            }
        }
        cout<<1;
    }
}






return 0;
}
