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

const int MN = 1 << 21 | 7;

int N;
char Str[MN];
int A[MN], B[MN], t;
int C[25], D[25];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int lst = 0;
        scanf("%s", Str + 1), N = strlen(Str + 1) + 1, t = 0;
        for (int i = 1; i < N; ++i)
            if (Str[i] == '^') A[++t] = i - lst, lst = i;
        A[++t] = N - lst, lst = N;
        for (int j = 0; j <= 20; ++j) C[j] = D[j] = 0;
        for (int i = 1; i <= t; ++i) {
            A[i] >>= 1;
            if (!A[i]) continue;
            B[i] = 31 - __builtin_clz(A[i]);
            ++C[B[i]], D[B[i]] = A[i];
        }
        int S = 0;
        for (int j = 20; ~j; --j) {
            if (C[j] >= 2) { S |= (1 << (j + 1)) - 1; break; }
            if (C[j]) {
                S |= 1 << j;
                int v = D[j] ^ 1 << j;
                if (!v) continue;
                int b = 31 - __builtin_clz(v);
                ++C[b], D[b] = v;
            }
        }
        printf("%d\n", S << 1 | (N & 1));
    }
    return 0;
}