#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define clr(x,y) memset(x,y,sizeof(x))
#define in(a) a=read()
#define out(a) printf("%d\n",a)
inline int read(){
    char c=getchar();int f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return x*f;
}
#define mod 998244353
void MOD(int &x){if(x>=mod)x-=mod;}
#define maxn 2100000
#define inf (1<<30)
char s[maxn];
int b[30],u[30];
int main(){
    int t;
    in(t);
    while(t--){
        clr(u,0);
        scanf("%s",s+1);
        int n=strlen(s+1);
        int sum=0,ans=0,w=0;
        s[0]=s[n+1]='^';
        FOR(i,1,n+1){
            if(s[i]=='?')sum++; 
            else{
                sum++;
                int j; 
                for(j=0;(1<<j)<=sum;j++){
                    if(sum&(1<<j))b[j]=1;
                    else b[j]=0;
                }
                j--;
                while(j){
                    if(b[j]){
                        if(!u[j])u[j]=1,b[j]--;
                        if(b[j])b[j-1]+=b[j]*2;
                    }
                    j--;
                }
                w+=b[0];w%=2;
                sum=0;
            }
        }
        FOR(i,1,21)
            if(u[i])
                ans+=(1<<i);
        if(w)ans++;
        out(ans);
    }
}