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

const int mo=1e9+7;
LL qpow(LL a,LL b)
{
    LL ans=1;
    a%=mo;
    while(b)
    {
        if(b&1)
            ans=ans*a%mo;
        b>>=1;
        a=a*a%mo;
    }
    return ans;
}

//----------------------------------

const int maxn=(1<<21)+5;
char s[maxn];
vector<int>v;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        v.clear();
        scanf("%s",s);
        int res=0;
        int i=0,j,k;
        int num=0;
        while(s[i]&&s[i]=='^')
        {
            num++;
            i++;
        }
        
        if(s[i]==0)
        {
            if(num&1)
                printf("0\n");
            else 
                printf("1\n");
            continue;    
        }
        
        if(num&1)
        {
            res^=1;
        }
        
        num=1;
        char last='?';
        for(i++;s[i];i++)
        {
            if(s[i]==last)
                num++;
            else
            {
                if(last=='^')
                {
                    if(num&1);
                    else
                        res^=1;
                }
                else
                {
                    if(num&1);
                    else
                        res^=1;
                    v.push_back(num+1>>1);
                }
                num=1;
                last=s[i];
            }
        }
        if(last=='^')
        {
            if(num&1)
                res^=1;
        }
        else
        {
            if(num&1);
            else
                res^=1;
            v.push_back(num+1>>1);
            num=0;
        }
        
        if(v.size())
        {
            sort(v.begin(),v.end(),greater<int>());
            int ans=v[0],x;
            int p[21],cnt;
            
            for(i=1;i<v.size();i++)
            {
                x=v[i];
                cnt=0;
                while(x)
                {
                    p[cnt++]=x&1;
                    x>>=1;
                }
                
                for(j=cnt-1;j>=0;j--)
                {
                    if((ans>>j&1))
                    {
                        if(p[j]==1)
                        {
                            ans|=(1<<j)-1;
                            break;
                        }
                    }
                    else 
                    {
                        if(p[j]==1)
                            ans|=1<<j;
                    }    
                }
            }
            printf("%d\n",(ans<<1)^res);
        }
        else
            printf("%d\n",res);
    }
    return 0;
}

/*
100
^??^????^^^
*/