#include <bits/stdc++.h>

using namespace std;

char s[3000007];

priority_queue<int> q;

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        while (!q.empty()) q.pop();
        scanf(" %s", s + 1);
        int L = strlen(s + 1);
        L++;
        int cnt = 0;
        int now = 1;
        for (int i = 1; i < L; i++)
        {
            if (s[i] == '?')
            {
                now++;
            }
            else
            {
                q.push(now);
                now = 1;
            }
        }
        q.push(now);
        int x = q.top();
        int k = 1;
        int ans = 0;
        while (k + k <= x) k += k;
        while (k > 1)
        {
            x = q.top();
            if (x >= k)
            {
                q.pop();
                q.push(x - k);
                ans |= k;
            }
            k >>= 1;
        }
        ans |= (L & 1);
        printf("%d\n", ans);
    }
    return 0;
}