#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mem(x,v) memset(x,v,sizeof(x))
#define Rep(i,a,b) for(register int i=(a);i<=int(b);++i)
#define rep(i,a,b) for(register int i=(a);i<int(b);++i)
#define Dep(i,a,b) for(register int i=(a);i>=int(b);--i)
#define gc getchar
#define pc putchar
#define fi first
#define se second
inline ll read(){
    ll x=0,f=1;char c=gc();
    for(;!isdigit(c);c=gc())if(c=='-')f=-1;
    for(;isdigit(c);c=gc())x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
inline void write(ll x){if(x<0)x=-x,pc('-');if(x>=10)write(x/10);putchar(x%10+'0');}
inline void writeln(ll x){write(x);pc('\n');}
inline void wri(ll x){write(x);pc(' ');}
#define link LINK
const int maxv = 505;
char s[5000000];
int vec[5000000];
void solve(){
    scanf("%s",s);
    *vec = 0;
    int cnt = 0;
    for(int i=0;s[i];++i){
        cnt++;
        if(s[i] == '^') vec[++*vec] = cnt,cnt = 0;
    }cnt++;vec[++*vec] = cnt;
    sort(vec+1,vec+1+*vec);
    reverse(vec+1,vec+1+*vec);
    
//    Rep(i,1,*vec) wri(vec[i]);puts("");
    
    int ans = 0;
    Rep(i,1,*vec){
        int x = vec[i];
        int t = 1.0*log(x)/log(2) + 1;
    //    writeln(t);
        while(t>=0){
    //        printf("{%d %d}\n",ans^(1<<t),ans);
            if(x >= (1<<t) && (ans ^ (1<<t)) > ans){
                ans ^= 1<<t;
                x -= 1<<t;
            }
            t--;
        }
    //    printf("x = %d\n",x);
        ans ^= (x & 1);
    }
    writeln(ans);
}
int main(){
    int T = read();
    while(T--){
        solve();
    }
    return 0;
}