#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,k,l,t,s,ans,T,mx;
char st[3000005];
int f[105];
int main(){
    scanf("%d",&T);
    while(T--){
        mx=0;
        memset(f,0,sizeof(f));
        scanf("%s",st+1);
        ans=0;
        s=1;n=strlen(st+1);
        for (int i=1;i<=n+1;i++){
            if(i>n||st[i]=='^'){
                int k=0;
                while(s){
                    k++;
                    if(f[k])f[k]+=(s&1)*k;else f[k]=s&1;
                    s/=2;
                }mx=max(mx,k);
                s=1;
            }else s++;
        }
        if(f[1]&1)ans=1;
        for (int i=mx;i>1;i--)if(f[i]){
            ans+=1<<i-1;
            f[i-1]+=f[i]-1;
        }
        printf("%d\n",ans);
    }
}