#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

char ch[2100000];
int T, l, n, cnt, now;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%s", ch);
        int l = strlen(ch);
        ch[l] = '^';
        ch[++l] = '\0';
        now = 0;
        cnt = 1;
        for (int i = 0; ch[i] != '\0'; ++i)
            if (ch[i] == '^') {
                cnt >>= 1;
                int tmp = now;
                now = 0;
                for (int j = 0; j <= cnt; ++j)
                    now = (tmp ^ j) > now ? tmp ^ j : now;
                cnt = 1;
            } else
                ++cnt;
        printf("%d\n", (now << 1) ^ (l & 1));
    }
    return 0;
}