#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 2100000;

char s[maxn];
int L,n;
int ret = 0;
vector<int> a;

int POW[30];

void init()
{
    gets(s);
    L = strlen(s);
    int tmp = 0;
    a.clear();
    ret = 0;
    for( int i = 0; i < L; i++ )
    {
        if ( s[i] == '?' ) tmp++;
        else{
            if ( tmp == 0 ) ret++;
            else{
                if(tmp%2==0) ret++ , a.push_back(tmp);
                else a.push_back(tmp+1);
            }
            tmp = 0;
        }
    }
    if ( tmp == 0 ) ret++;
    else if(tmp%2==0) ret++ , a.push_back(tmp);
         else a.push_back(tmp+1);
    sort(a.begin(),a.end());

}

inline int getf(int x)
{
    for( int i = 22; i >= 1; i-- )
        if ( x >= POW[i] ) return i;
    return 1;
}

int solve()
{
    int ans = 0;
    bool bit[30];
    for( int i = 0; i < 30; i++ ) bit[i] = false;
    n = a.size();
    //for( int i = 0; i < n; i++ ) printf("%d  ", a[i]);
    for( int i = n-1; i >= 0; i-- )
    {
        int sum = 0;
        int j = getf(a[i]);
        while(j>=1)
        {
            if ( bit[j] ) j--;
            else{
                if ( sum+POW[j]<=a[i] ) sum+=POW[j] , bit[j] = true;
                j--;
            }
        }
    }
    for( int i = 1; i <= 22; i++ )
        if ( bit[i] ) ans += POW[i];
    ans += ret&1;
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    getchar();
    POW[0] = 1;
    for( int i = 1; i < 30; i++ ) POW[i] = POW[i-1]*2;
    while(T--)
    {
        init();
        printf("%d\n",solve() );
    }
    return 0;
}