#include <bits/stdc++.h>
using namespace std;
const int maxn = 2200000;
char s[maxn];
int x[maxn],tot,vis[30];
int main(void) {
//    freopen("c.in","r",stdin);
    int T; scanf("%d",&T);
    while (T--) {
        tot=0;
        scanf("%s",s+1);
        int n = strlen(s+1);
        int tmp=1;
        for (int i=1;i<=n;i++) {
            if (s[i] == '?') {
                tmp++;
            } else {
                x[tot++]=tmp;
                tmp=1;
            }
        }
        x[tot++]=tmp;
        sort(x,x+tot,greater<int>());
//        printf("x : ");
//        for (int i=0;i<tot;i++) printf("%d ",x[i]); puts("");
        int o=0, ans=0;
        memset(vis,0,sizeof(vis));
        for (int i=0;i<tot;i++) {
            for (int j=21;j>=1;j--) if (!vis[j] && (x[i] >= (1<<j))) {
                vis[j] = 1;
//                printf("j = %d\n",j);
                x[i] -= (1<<j);
            }
            o ^= (x[i]&1);
        }
        for (int i=21;i>=1;i--) if (vis[i]) ans |= (1<<i);
        ans |= o;
        printf("%d\n",ans);
    }
    return 0;
}

//x1 ^ x2 ^ x3 ...