#include<bits/stdc++.h>  
using namespace std;
typedef long long ll;
#define ri register int
int n,m,t,i,j,p[25],k,ans;
char c[3000005];
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",c);
        memset(p,0,sizeof(p));
        for(i=0;c[i];i++)
        {
            for(j=i;c[j]=='?';j++);
            int s=j-i+1;
            for(k=1;(1<<k)<=s;k++);
            for(k--;k>=1;k--)
                if(p[k]==0&&s>=(1<<k))
                {
                    s-=(1<<k);
                    p[k]=1;
                }
            i=j;
        }
        ans=0;
        for(i=23;i>=1;i--)
            if(p[i])
                ans+=(1<<i);
        if(strlen(c)%2==1)
            printf("%d\n",ans);
        else
            printf("%d\n",ans+1);
        for(i=0;c[i];i++)
            c[i]=0;
    }
}