#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int mod=998244353;
inline int add(int a,int b)
{
    a+=b;
    if(a>=mod)a-=mod;
    return a;
}
inline int dec(int a,int b)
{
    a-=b;
    if(a<0)a+=mod;
    return a;
}
inline int mult(int a,int b)
{
    ll t=1ll*a*b;
    if(t>=mod)t%=mod;
    return t;
}
inline int power(int a,int b)
{
    int out=1;
    while(b)
    {
        if(b&1)out=mult(out,a);
        a=mult(a,a);
        b>>=1;
    }
    return out;
}
int T,cnt[26];
char s[1<<21];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        int len=strlen(s+1);
        int ncnt=1,out=0;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=len;i++)
        {
            if(s[i]=='^')
            {
                for(int i=0;(1<<i)<=ncnt;i++)if((ncnt>>i)&1)cnt[i]++;
                ncnt=1;
            }
            else ncnt++;
        }
        for(int i=0;(1<<i)<=ncnt;i++)if((ncnt>>i)&1)cnt[i]++;
        int l=0;
        while((1<<l)<=len+1)l++;
        l--;
        for(int i=l;i>=1;i--)if(cnt[i])out|=(1<<i),cnt[i-1]+=2*(cnt[i]-1);
        if(cnt[0]&1)out++;
        printf("%d\n",out);
    }
    return 0;
}