#include<bits/stdc++.h>
using namespace std;
int dp[1<<21+1][2];
char s[1<<21+1];
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%s", s+1);
        int len = strlen(s+1);
        s[0] = '^';
        int sum = 1;
        int cnt = 0;
        vector<int> vec;
        for(int i = 1; i <= len; ++i){
            if(s[i] == '?'){
                cnt++;
            }
            else{
                sum = max(sum, cnt+1);
                if(cnt)
                 vec.push_back(cnt+1);
                cnt = 0;
            }
            if(s[i] == s[i-1] && s[i] == '^') vec.push_back(1);
        }
        if(cnt)
                vec.push_back(cnt+1);
        if(s[len] == '^') vec.push_back(1);
        sum = max(sum, cnt);
        int ans = 0;
        for(int i = 0; i < vec.size(); ++i){
            if(vec[i] == 1) ans ^= 1;
            else{
                int j;
                int ss = vec[i];
                for(j = 21; j >= 0; --j){
                    if( !((1<<j)&ans)&& (1<<j) <= ss) {
                        ans |= (1 << j);
                        ss -= (1 << j);
                    }
                }
                if(ss&1) ans ^= 1;
            }
        }
        printf("%d\n", ans);

    }
    return 0;
}
/*
1+1+1^1?1
101
*/