#include <bits/stdc++.h>
using namespace std;
const int maxn = 2097153;
int T, n, cnt[maxn];
int Hi2[maxn];
char s[maxn];
int main() {
    Hi2[1] = 1;
    for (int i = 2; i < maxn; ++i) Hi2[i] = Hi2[i >> 1] << 1;
    for (scanf("%d", &T); T--; ) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        for (int i = 0; i <= n; ++i) cnt[i] = 0;
        for (int i = 1, cur = 0; i <= n; ++i) {
            if (s[i] == '?') ++cur;
            if (s[i] == '^' || i == n) ++cnt[cur], cur = 0;
        }
        int ans = 0;
        for (int i = n; i >= 0; --i) {
            if (cnt[i] > 1) ans |= ((Hi2[i + 1] << 1) - 1);
        }
        for (int i = n; i >= 0; --i) {
            if (cnt[i] == 1) {
                int j = i + 1;
                while (j) {
                    if (ans & Hi2[j]) {
                        ans |= (Hi2[j] - 1);
                        break;
                    } else {
                        ans |= Hi2[j];
                        j -= Hi2[j];
                    }
                }
            }
        }
        (ans >>= 1) <<= 1;
        ans ^= ((n & 1) ^ 1);
        printf("%d\n", ans);
    }
    return 0;
}