#include<bits/stdc++.h> 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define fi first
#define se second
#define PB push_back
#define uint unsigned
#define ull unsigned ll 
using namespace std;
int q[5000005];
char s[5000005];
void solve(){
    scanf("%s",s+1);
    *q=0;
    int n=strlen(s+1),res=1;
    For(i,1,n)
        if (s[i]=='?') res++;
        else q[++*q]=res,res=1;
    q[++*q]=res;
    sort(q+1,q+*q+1);
    int ans=0;
    Rep(i,*q,1){
        for (;q[i]>=2&&(q[i]&ans&((1<<30)-2));q[i]-=2);
        ans^=q[i];
    }
    printf("%d\n",ans);
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--) solve();
}