#include <cstdio>
#include <cstring>
#include <algorithm>

int T;
char s[3000000];
int len;
int cc[3000000];
int mx;
int ans;

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%s", s + 1);
        len = strlen(s + 1);
        int pre = 1;
        int cnt = 0;
        for (int i = 1; i <= len + 1; i++)
        {
            cc[i] = 0;
        }
        mx = 0;
        for (int i = 1; i <= len; i++)
        {
            if (s[i] == '?')
            {
                pre++;
            }
            else
            {
                cc[pre]++;
                mx = std::max(mx, pre);
                pre = 1;
            }
        }
        cc[pre]++;
        mx = std::max(mx, pre);
        ans = 0;
        for (int i = 20; i >= 1; i--)
        {
            if ((1 << i) <= mx)
            {
                ans += (1 << i);
                cc[mx]--;
                cc[mx - (1 << i)]++;
                while (cc[mx] == 0 && mx >= 1)
                {
                    mx--;
                }
            }
        }
        int s = 0;
        for (int i = 1; i <= len + 1; i++)
        {
            s += i * cc[i];
        }
        ans += (s & 1);
        printf("%d\n", ans);
    }
    return 0;
}