#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
 
#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>
 
#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = (1 << 21) + 5;

int n, m;
int c[N], dig[N];
int bas[22], cnt[22];
char s[N];

void solve() {
  scanf("%s", s);
  n = strlen(s);
  m = 0;
  int cc = 1;
  for (int i = 0; i < n; ++i) {
    if (s[i] == '^') {
      c[++m] = cc;
      cc = 1;
    } else
      ++cc;
  }
  c[++m] = cc;
  int ans = 0;
  memset(cnt, 0, sizeof(cnt));
  memset(bas, 0, sizeof(bas));
  int mxd = -1;
  for (int i = 1; i <= m; ++i) {
    ans ^= c[i] & 1;
    c[i] >>= 1;
    if (c[i]) {
      mxd = max(mxd, dig[c[i]]);
      bas[dig[c[i]]] = max(bas[dig[c[i]]], c[i]);
      ++cnt[dig[c[i]]];
    }
  }
  if (mxd == -1) printf("%d\n", ans);
  else {
    int la = bas[mxd];
    if (cnt[mxd] > 1) la = (1 << (mxd + 1)) - 1;
    cnt[mxd] = 1;
    for (int i = mxd - 1; i >= 0; --i) {
      if (cnt[i]) {
        if (!((la >> i) & 1)) {
          if (cnt[i] > 1) {
            la |= (1 << (i + 1)) - 1;
            break;
          } else {
            for (int j = i; j >= 0; --j) {
              if ((la >> j) & 1) {
                if ((bas[i] >> j) & 1) {
                  la |= (1 << j) - 1;
                  break;
                }
              } else if ((bas[i] >> j) & 1)
                la |= 1 << j;
            }
          }
        } else
          la |= (1 << (i + 1)) - 1;
      }
    }
    printf("%d\n", (la << 1) ^ ans);
  }
}

int main() {
  for (int i = 0; i < 21; ++i)
    for (int j = (1 << i); j < (1 << (i + 1)); ++j) dig[j] = i;
  int t;
  scanf("%d", &t);
  while (t--) solve();
  return 0;
}