#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;



int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;

    while (T--) {
        string s;
        cin >> s;

        int n = (int)s.size();
        vector<vector<ll>> suff_time(n + 1, vector<ll>(2));

        std::function<ll(int, int)> Solve = [&](int l, int r) -> ll {

            if (l == r) {
                return 0;
            }

            if (l == r - 1) {
                return s[l] == '1' ? 1 : 2;
            }

            int mid = (l + r) / 2;
            ll answer = Solve(l, mid) + Solve(mid, r);

            vector<ll> cnt(2);
            vector<ll> sum(2);

            suff_time[mid][0] = 0;
            suff_time[mid][1] = 0;

            for (int i = mid - 1; i >= l; i--) {
                if (s[i] == '1') { // green
                    suff_time[i][0] = suff_time[i + 1][1] + 1;
                    suff_time[i][1] = suff_time[i + 1][1] + 2;
                } else { // red
                    suff_time[i][0] = suff_time[i + 1][0] + 2;
                    suff_time[i][1] = suff_time[i + 1][0] + 1;
                }
                cnt[suff_time[i][0] % 2]++;
                sum[suff_time[i][0] % 2] += suff_time[i][0];
            }
            
            vector<ll> t(2);
            t[0] = 0;
            t[1] = 1;

            auto Go = [](ll& t, char x) {
                if (x == '1') {
                    // (i, 0) -> (i + 1, 1) +1
                    // (i, 1) -> (i + 1, 1) +2

                    if (t % 2 == 0) {
                        t++;
                    } else {
                        t += 2;
                    }
                } else {
                    // (i, 0) -> (i + 1, 0) +2
                    // (i, 1) -> (i + 1, 0) +1

                    if (t % 2 == 1) {
                        t++;
                    } else {
                        t += 2;
                    }
                }
            };

            for (int i = mid; i < r; i++) {
                Go(t[0], s[i]);
                Go(t[1], s[i]);
                answer += (t[1] - 1) * cnt[1] + sum[1];
                answer += t[0] * cnt[0] + sum[0];
            }

            return answer;
        };

        cout << Solve(0, n) << "\n";
    }

    return 0;
}