#include<bits/stdc++.h>

char c;
bool a[25];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        while(c != '?' && c != '^') c = getchar();
        int ans = 0, now = 1;
        memset(a, false, sizeof(a));
        while(c == '?' || c == '^')
        {
            if (c == '^')
            {
                for(int i = 20; i >= 1; i--)
                    if (!a[i] && now >= 1 << i)
                        now -= 1 << i, a[i] = true;
                ans += now;
                now = 1;
            }
            if (c == '?') now++;
            c = getchar();
        } 
        for(int i = 20; i >= 1; i--)
            if (!a[i] && now >= 1 << i)
                now -= 1 << i, a[i] = true;
        ans += now;
        
        ans &= 1;
        for(int i = 1; i <= 20; i++)
            if (a[i]) ans += 1 << i;
        
        printf("%d\n", ans);
    }
    return 0;
}