#include<bits/stdc++.h>
using namespace std;

char s[1<<21];
vector<int> v;

int main(){
    for( int T ; scanf( "%d" , &T )==1 ; ){
        for( int cas=1 ; cas<=T ; cas++  ){
            scanf( "%s" , s );
            v.clear();
            int len = strlen(s),cnt = 0,last = -1;
            for( int i=0 ; i<=len ; i++ ){
                if( i==len||s[i]=='^' ){
                    int t = i-last;
                    last = i;
                    cnt = (cnt+t)%2;
                    v.push_back(t);
                }
            }
            int ans = 0;
            for( int i=20,j=1024*1024 ; i>=1 ; i--,j>>=1 ){
               int tmp = 0;
               for( int k=0 ; k<v.size() ; k++ )
                    if( v[k]&j ){
                        tmp++;
                    }
                if( tmp==1 ){
                    ans += j;
                }else if( tmp>=2 ){
                    ans += j*2-2; break;
                }
            }
            printf( "%d\n" , ans+cnt );
        }
    }
    return 0;
}