#include<bits/stdc++.h>
using namespace std;
#define res register int
#define fz(a,b) memset(a,b,sizeof a)
#define qd(a) while(!a.empty())a.pop()
#define JB(a,b)(T[++t]=b,E[t]=H[a],H[a]=t)
#define ll long long
#define N 2100000
#define M 52
char S[N];
int T,a,b,k,s,w,t,m,A[N];
int CZ(int x){
    for(int i=21;i>=0;i--)
        if(x&(1<<i))return i;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",S+1),s=strlen(S+1);
        int t=1,w=0;
        for(int i=1;i<=s;i++)if(S[i]=='?')t++;
            else A[++w]=t,t=1;
        A[++w]=t;
        if(w==1){
            printf("%d\n",t);
            continue;
        }
        t=A[1],m=CZ(t);
        for(int i=2;i<=w;i++){
            for(int j=21;j>m;j--)if(A[i]&(1<<j)&&!(t&(1<<j)))t+=1<<j;
            for(int j=m;j>=1;j--)if(A[i]&(1<<j)){
                if(!(t&(1<<j)))t+=1<<j;
                else{
                    for(int k=j-1;k>=1;k--)if(!(t&(1<<k)))t+=1<<k;
                    break;
                }
            }
            m=CZ(t);
            if(A[i]%2==1)t^=1;
        }
        printf("%d\n",t);
    }
    return 0;
}