#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
priority_queue<int>q;
char s[4000010];
int main()
{
    int cas;
    scanf("%d",&cas);
    while (cas--)
    {
        scanf("%s",s+1);
        while (!q.empty()) q.pop();
        int n=strlen(s+1);
        int last=0;
        for (int i=1;i<=n;i++)
        {
            if (s[i]=='^') q.push(i-last),last=i;
        }
        q.push(n+1-last);
        if (last==0)
        {
            printf("%d\n",n+1);
            continue;
        }
        int ans=0;
        for (int i=21;i>=0;i--)
        {
            int tmp=1<<i;
            if (q.top()<tmp) continue;
            int a1=q.top();
            q.pop();
            int a2=q.top();
            if (a2>=tmp)
            {
                for (int j=i;j>=0;j--)
                {
                    ans+=1<<j;
                }
                if ((n+1)&1) printf("%d\n",ans);
                else printf("%d\n",ans-1);
                goto fail;
            }
            a1-=tmp;
            ans+=tmp;
            q.push(a1);
        }
        printf("%d\n",ans);
        fail:;
    }
    return 0;
}