#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;

void process()
{
    string s;
    cin >> s;

    char last = s[0];
    vector<int> lens;
    int len = 1;
    
    int used = 0;
    int res = s[0] == '^' ? 1 : 0;

    for (int i = 1; i <= s.length(); ++i) {
        if (i < s.length() && s[i] == last) {
            ++len;
            continue;
        }

        if (last == '^') {
            if (len % 2 == 0) {
                len = 2;
            } else {
                len = 1;
            }

            if (i == s.length()) {
                if (len == 1) res ^= 1;
            } else {
                if (len == 2) res ^= 1;
            }
        } else {
            int t = len + 1;
            for (int j = 20; j > 0; --j) {
                if ((!((used >> j)&1)) && (t >= (1<<j))) {
                    t -= 1 << j;
                    res += 1 << j;
                    used |= 1 << j;
                }
            }

            t &= 1;
            res ^= t;
        }

        if (i < s.length()) {
            last = s[i];
            len = 1;
        }
    }

    cout << res << endl;
}

int main(void)
{
    int T;
    cin >> T;
    for (int i = 1; i <= T; ++i)
    {
        process();
    }
    return 0;
}