Untitled

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define endl '\n'


#define file(in, out)                                                        \
  freopen(in, "r", stdin);                                                     \
  freopen(out, "w", stdout)

#define FIn                                                                    \
  cin.tie(0);                                                                  \
  cout.tie(0);                                                                 \
  ios_base::sync_with_stdio(false)

int tc;
const bool MULTI_TESTS = true;
const string IN = "input.txt";
const string OUT = "output.txt";
const int N = 1e6 + 10;
const int MOD = 1e9 + 7;

void pre();

//check MAX_N
int n;
string s;

void solve() {
    vector<ll> diff;
    cin >> s;
    n = s.size();
    diff.resize(n + 5);

    for(int i = 0; i < n; ++i){
        if(s[i] == '0')
            continue;

        ll prf = i + 1;
        ll lstPos = n - i;
        diff[0] += prf;
        diff[lstPos] -= prf;
    }

    for(int i = 1; i < n + 2; ++i)
        diff[i] += diff[i - 1];

    ll carry = 0;
    string ans;
    for(int i = 0; i < n + 1; ++i){
        diff[i] += carry;

//        if(diff[i] == 0)
//            break;

        ans.push_back(char((diff[i] & 1ll) + '0'));

        carry = diff[i] / 2;
    }
    reverse(all(ans));
    cout<<ans<<'\n';

}

int main() {
    FIn;
#ifndef ONLINE_JUDGE
    file(IN.c_str(), OUT.c_str());
#endif

    tc = 1;
    if (MULTI_TESTS) cin >> tc;
    pre();

    for (int i = 1; i <= tc; i++) {
        // cout << "Case " << i <<": \n";
        solve();
    }
}

void pre() {



}