#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int maxn = 2e7+5;
char a[maxn];
int ji;
map<int,int> mp;
void Add(int cnt) {
    ji ^= cnt%2;
    int zz = 0;
    while (cnt>0) {
        ++zz;
      if (cnt%2) mp[+zz]++;
      cnt /= 2;
    }
    //mp[zz]++;
}
int main() {
    int T;
    scanf("%d", &T);
    for (int tt = 0; tt < T; ++tt) {
        ji = 0;
        mp.clear();
        scanf("%s", &a);
        int n = strlen(a);
        int cnt=1;
        for (int i=0;i<n;i++) {
            if (a[i]=='^') {
              Add(cnt);
              cnt = 1;
            } else {
              cnt++;
            }
        }
        Add(cnt);
        long long ans = 0;
        for (int i=32;i>=2;i--) {
            if(mp[i]>=2) {
                ans+= 1<<i;
                ans -= 2;
                break;
            } else if (mp[i] == 1) {
                ans += 1<<(i-1);
            }
        }
        ans += ji;
        cout << ans << endl;
    }
    return 0;
}