#include<bits/stdc++.h>
using namespace std;
const int N=(1<<21)+50;
int T,len;
char s[N];
int val[30];
int main()
{
    int i,j,num,len,bn,ans;
    scanf("%d",&T);
    while(T--)
    {
        memset(val,0,sizeof(val));
        scanf("%s",s+1);
        len=strlen(s+1);
        len++;s[len]='^';
        for(i=1,num=1;i<=len;i++)
        {
            if(s[i]=='^')
            {
                for(bn=0;(1<<(bn+1))<=num;bn++);
                for(j=bn;j>=1;j--)
                {
                    if(val[j]==0&&num>=(1<<j))
                    {
                        num-=(1<<j);val[j]=1;
                    }
                }
                num=1;
            }
            else
            {
                num++;
            }
        }
        ans=0;
        for(i=1;i<=24;i++)
        {
            if(val[i]) ans+=(1<<i);
        }
        if(len&1) ans++;
        printf("%d\n",ans);
    }
    return 0;
}