#include<bits/stdc++.h>
using namespace std;

const int mx =3e6;
int a[mx];
char s[mx];


int main()
{
    int t;
    cin>>t;
    while (t--)
    {
        scanf("%s",s);
        int p=0,cut=1;
        for (int i=0;s[i];i++)
        {
            if (s[i]=='?') cut++;
            else
            {
                a[p++]=cut;
                cut = 1;
            }
        }
        a[p++]=cut;
        int ans = 0,w = pow(2,21);
        while (w>1)
        {
            int cut = 0;
            for (int i=0;i<p;i++)
            {
                if (a[i]>=w)
                {
                    ans+=w;
                    a[i]-=w;
                    break;
                }
            }
            w/=2;
        }
        for (int i=0;i<p;i++)
        {
            ans ^=(a[i]%2);
        }
        cout<<ans<<endl;
    }
}