#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2.1e6 + 70;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double eps = 1e-7;
const double PI = acos(-1.0);

int n, m, k;

char s[maxn];

int a[maxn];

int main(){
    //freopen("in.txt", "r", stdin);
    int T;
    cin>>T;
    while(T--){
        scanf("%s",s+1);
        n=strlen(s+1);

        int f=0, cur=1, cnt=0;
        for(int i=1;i<=n+1;i++){
            if(s[i]=='?') cur++;
            else{
                f^=(cur&1);
                a[cnt++]=(cur>>1);
                cur=1;
            }
        }

        sort(a,a+cnt);
        //cout<<"a: ";for(int i=0;i<cnt;i++) cout<<a[i]<<" ";cout<<endl;

        int p=0, x=0;
        for(int c=22;c>=0;c--){
            for(int i=0;i<cnt;i++){
                if(a[i]>=(1<<c)){
                    a[i]-=(1<<c);
                    x+=(1<<c);
                    break;
                }
            }
        }
        //cout<<"x: "<<x<<endl;

        int ans=(x<<1)+f;
        cout<<ans<<endl;
    }
    return 0;
}