#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
char a[4500000];
int poww[25];
int vis[25];
vector<int>s;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        scanf("%s",a);
        int n=strlen(a);
        int ans=0;
        int sum=1;
        s.clear();
        for(int i=0;i<n;i++)
        {
            if(a[i]=='^')
            {
                s.push_back(sum);
                sum=1;
            }
            else if(a[i]=='?')
            {
                sum++;
            }
        }
        if(sum>0)s.push_back(sum);
        sort(s.begin(),s.end());
        for(int i=0;i<=24;i++)
        {
            if(i==0)poww[i]=1;
            if(i==1)poww[i]=2;
            if(i>1)poww[i]=poww[i-1]*2;
        }
        for(int i=s.size()-1;i>=0;i--)
        {
            //printf("--%d\n",s[i]);
            while(true)
            {
                int flag=0;
                for(int j=24;j>=0;j--)
                {
                    if(s[i]>=poww[j]&&vis[j]==0)
                    {
                        flag=1;
                        vis[j]=1;
                        s[i]-=poww[j];
                        ans=ans^poww[j];
                    }
                }
                if(flag==0)break;
            }
        }
        for(int i=0;i<s.size();i++)
        {
            if(s[i]%2==0)continue;
            else ans=ans^1;
        }
        printf("%d\n",ans);
    }
}