#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cerr << "\033[32;1m" << #x << " -> "; err(x); } while (0)
#else
#define dbg(...)
#endif // zerol
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
// ----------------------------------------------------------------------------------------

const int N = 21, M = 1 << N;

char s[M];
int a[M];

multiset<int> S;

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%s", s);
        int n = strlen(s);
        int pre = 1;
        FOR(i, 0, n+1) {
            if(s[i] == '?') {
                ++pre;
            } else {
                S.insert(pre);
                pre = 1;
            }
        }
        int ans = 0;
        FORD(i, 20, 0) {
            int x = 1<<i;
            if(S.empty()) break;
            auto it = S.rbegin();
            if(*it >= x) {
                ans +=x;
                int v = *it - x;
                S.erase(--S.end());
                if(v>0) S.insert(v);
            }
        }
        for(auto x: S) ans ^= x&1;
        printf("%d\n", ans);
        S.clear();
    }
    return 0;
}