An_pbinfo_dp

#include <bits/stdc++.h>

using namespace std;

ifstream fin("an.in");
ofstream fout("an.out");

int t;

int main()
{
    fin>>t;
    while(t)
    {
        int n;
        char s[10001];
        bool c[10001];
        fin>>s;
        n=strlen(s);
        c[n-1]=1;
        for (int i=n-2; i>=0; i--)
            if(s[i]!=s[i+1])
                c[i]=1-c[i+1];
            else
                c[i]=1;
        fout<<c[0]<<'\n';
        t--;
    }
    return 0;
}