#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6;
int t, n;
int stat, mx;
char s[maxn + 10];

void addin(int x) {
    for (int i = 25; i > mx; --i)
        if (x >> i & 1) {
            if (stat >> i & 1) {
                for (int j = mx + 1; j <= i; ++j)
                    stat |= 1 << j;
                mx = i; return;
            } else stat |= 1 << i;
        }
}

int main() {
    scanf("%d", &t);
    while (t--) {
        stat = 0; mx = -1;
        scanf("%s", s + 1);
        n = strlen(s + 1);
        int cnt = 1;
        for (int i = 1; i <= n; ++i) {
            if (s[i] == '^') {
                addin(cnt); cnt = 0;
            }
            ++cnt;
        }
        addin(cnt);
        printf("%d\n", (stat / 2 * 2) | (~n & 1));
    }
}