#include<bits/stdc++.h>
using namespace std;
#define MAXN 2097152
char c[MAXN];
int T,n,m,i,j,k,ans,s[MAXN];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",c);
        n=strlen(c);
        ans=n+1&1;
        fill(s,s+n+2,0);
        for(i=j=m=0;i<n;i++)if(c[i]=='^')
        {
            s[i-j+1>>1]++;
            j=i+1;
        }
        s[i+1-j>>1]++;
        for(i=n+1;i;i--)while(s[i])
        {
            for(j=i,k=19;~k;k--)if(j>=(1<<k)&&!(ans>>k+1&1))
            {
                ans|=1<<k+1;
                j-=1<<k;
            }
            s[i]--;
        }
        printf("%d\n",ans);
    }
    return 0;
}