#include<bits/stdc++.h>
using namespace std;
const int M=1<<21|5;

int n;
char str[M];

int Cnt[M];
void Deal(int x)
{
    while(x)
    {
        Cnt[x&-x]++;
        // printf("%d ++\n",x&-x);
        x&=x-1;
    }
}
void Solve()
{
    for(int i=0;i<=20;i++)Cnt[1<<i]=0;
    int l=0;
    for(int i=1;i<=n;i++)
    {
        ++l;
        if(str[i]=='^')Deal(l),l=0;
    }
    ++l;Deal(l);
    int ans=0,c=0;
    for(int i=20;i>=1;i--)
    {
        bool f=false;
        if(c)ans|=1<<i,f=true;
        c+=Cnt[1<<i];
        if(!f and c)ans|=1<<i,c--;
    }
    ans|=Cnt[1]&1;
    printf("%d\n",ans);
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%s",str+1);n=strlen(str+1);
        Solve();
    }
    return 0;
}