#include<bits/stdc++.h>
using namespace std;
char s[(1<<21)+10];
int main()
{
    int r[25];
    bool u[25];
    r[0]=1;
    for(int i=1;i<=24;i++)r[i]=r[i-1]*2;
    int t;
    scanf("%d",&t);
    {
        while(t--)
        {
            scanf("%s",s+1);
            int cnt=0;
            int xors=0;
            int ans=0;
            memset(u,0,sizeof(u));
            int l=strlen(s+1);
            if(s[1]=='^')xors^=1;
            if(s[l]=='^')xors^=1;
            for(int i=1;i<=l;i++)
            {
                cnt++;
                if(s[i+1]!=s[i])
                {
                    if(s[i]=='?')
                    {
                        cnt=cnt+1;
                        for(int i=24;i>=0;i--)
                        {
                            if(cnt>=r[i]&&u[i]==0)
                            {
                                u[i]=1;
                                cnt-=r[i];
                                ans+=r[i];
                            }
                        }
                        xors^=cnt&1;
                    }
                    if(s[i]=='^')
                    {
                        cnt=cnt-1;
                        xors^=cnt&1;
                    }
                    cnt=0;
                }
            }
            ans^=xors;
            printf("%d\n",ans);
        }
    }
    return 0;
}