#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
    int T;
    cin>>T;
    while(T--) {
        cin>>s;
        int t=0;
        vector<int> vec;
        for(int i=0;s[i];i++) {
            if(s[i]=='^'&&t) vec.push_back(t+1),t=0;
            else if(s[i]=='?')t++;
        }
        if(t) vec.push_back(t+1);
        int ans=0,x=0;
        for(int i=0;i<vec.size();i++) {
            for(int j=25;j>=1;j--)
                if((1<<j)<=vec[i]&&!((1<<j)&ans)) {
                    ans|=(1<<j);
                    vec[i]-=(1<<j);
                    x+=(1<<j);
                }
        }
        if((s.size()+1-x)&1) ans++;
        printf("%d\n",ans);
    }
    return 0;
}