#include<bits/stdc++.h>
#define N 2097160
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cout<<#x<<"="<<x<<endl;
#define db2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
using namespace std;
int T,n,a[N];
char s[N];
priority_queue<int>q;
int main() {
    scanf("%d",&T);
    while(T--) {
        int now=1;
        scanf("%s",s+1),n=strlen(s+1)+1;
        for(int i=1; i<n; i++) {
            //i  s[i]  i+1
            if(s[i]=='^') {
                q.push(now);
                now=1;
            } else now++;
        }
        q.push(now);
        int ans=0;
        for(int i=20; i>=0; i--) {
            while(1<<i+1&q.top()) {
                now=q.top(),q.pop();
                q.push(now/2),q.push(now/2+(now&1));
            }
            if(1<<i&q.top()) {
                now=q.top(),q.pop();
                ans+=1<<i,q.push(now^(1<<i));
            }
        }
        while(!q.empty()) {
            ans^=q.top(),q.pop();
        }
        printf("%d\n",ans);
//        for(int i=1;i<=tot;i++)printf("%d ",a[i]);
//        puts("");

    }
    return 0;
}