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

const int N = 1 << 21;

int T, n, lg2[N];
char s[N];

int main()
{
    scanf("%d", &T);
    for (int i = 2; i < N; ++i)
        lg2[i] = lg2[i >> 1] + 1;
    while (T--)
    {
        scanf("%s", s);
        int ans = 0;
        vector<int> v;
        int lst = -1;
        for (int i = 0; ; ++i)
        {
            if (!s[i] || s[i] == '^')
            {
                v.push_back(i - lst);
                if (i - lst & 1) ans ^= 1;
                lst = i;
            }
            if (!s[i]) break;
        }
        int cnt[21] = {};
        for (int x : v)
            for (int i = lg2[x]; i; --i)
                if (x >> i & 1)
                    ++cnt[i];
        for (int i = 20; i; --i)
        {
            if (!cnt[i]) continue;
            if (cnt[i] == 1)
                ans |= 1 << i;
            else
            {
                for (; i; --i)
                    ans |= 1 << i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}