#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+233;
int T,n,m,c,ok,t,add,ret,ans,sum,tot;
int a[maxn],flag[maxn],idx[maxn];
char str[2330000];
int read()
{
   int v=0,f=1;
   char c=getchar();
   while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
   while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
   return v*f;
}
int solve(char *str,int &len)
{
    ans=0,add=1;
    for(int i=1; i<=len; ++i)
    {
        if(str[i]=='?')
            add++;
        else
        {
            for(int j=22; j>=1; --j)
            {
                t = (1<<j);
                if(add >= t && !(ans&t))
                {
                    ans |= t;
                    add -= t;
                }
            }
            add = 1;
        }
    }
    for(int j=22; j>=1; j--)
    {
        t = (1<<j);
        if(add >= t && !(ans&t))
        {
            ans |= t;
            add -= t;
        }
    }
    if(len%2==0) ans^=1;
    return ans;
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",str+1);
        int len = strlen(str+1);
        ret = solve(str,len);
        printf("%d\n",ret);
    }
    return 0;
}