#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int MAXN=3000005;

int n;
char s[MAXN];
int m,a[MAXN],_log2[MAXN];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("code.in","r",stdin);
    //freopen("code.out","w",stdout);
    #endif
    int T;
    scanf("%d",&T);
    while(T--)
    {
        m=0;
        scanf("%s",s+1);
        n=strlen(s+1);
        _log2[1]=0;
        for(int i=2;i<=n;i++)
            _log2[i]=_log2[i-1]+((1<<(_log2[i-1]+1))==i);
        int cur=1;
        for(int i=1;i<=n;i++)
            if(s[i]=='^'){a[++m]=cur;cur=1;}
            else ++cur;
        a[++m]=cur;
        sort(a+1,a+m+1);
        cur=0;
        int las=0;
        for(int i=m;i>0;i--)
        {
            if(a[i]&1)las^=1;
            if(cur&a[i])cur|=((1<<_log2[cur&a[i]])-1);
            cur|=a[i];
        }
        if((cur&1)!=las)printf("%d\n",cur-1);
        else printf("%d\n",cur); 
    }
    return 0;
}