#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
#define rep(i,a,b) for(int i=(a),i##_end_=(b);i<=i##_end_;i++)
#define dwn(i,a,b) for(int i=(a),i##_end_=(b);i>=i##_end_;i--)
using namespace std;
inline int read() {
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1010;
int f[maxn][maxn];
int A[1<<21],m,tmp[30];
char str[1<<21];
int main() {
/*    int n=20;
    f[0][1]=1;
    rep(i,1,n) {
        rep(j,0,i-1) {
            rep(a,0,i+1) rep(b,0,i+1) {
                if(f[j][a]&&f[i-j-1][b]) {
                    f[i][a+b]=1;
                    f[i][a^b]=1;
                }
            }
        }
        printf("%d :: ",i);
        rep(j,0,i+1) if(f[i][j]) printf("%d ",j);puts("");
    }*/
    int T=read();
    while(T--) {
        scanf("%s",str+1);m=0;
        int n=strlen(str+1);
        int la=0;
        rep(i,1,n) {
            if(str[i]=='^') {
                A[++m]=i-la;
                la=i;
            }
        }
        A[++m]=n+1-la;
        int f=0,ans=0;
        memset(tmp,0,sizeof(tmp));
        rep(i,1,m) {
        //    printf("%d ",A[i]);
            if(A[i]%2) f^=1;
            A[i]/=2;
            rep(j,0,22) {
                if(A[i]<(1<<j)) break;
                if(A[i]>>j&1) tmp[j]++;
            }
        }
        dwn(i,22,0) {
            if(tmp[i]==1) ans^=1<<i;
            else if(tmp[i]>1) {
                rep(j,0,i) ans^=1<<j;
                break;
            }
        }
        printf("%d\n",ans*2+f);
    }
    return 0;
}