#include <bits/stdc++.h>   using namespace std;      int main()   {    ios_base::sync_with_stdio(false), cin.tie(0);    int t;    cin >> t;    while (t--) {     map<int, int>L, R;     int bal = 0;     string s;     cin >> s;     for (char &c : s) {      if (c ==  1 ) {       R[bal]++;       bal++;      } else {       L[bal]++;       bal--;      }     }        int cur = 0;     while (L[cur] > 0 || R[cur] > 0) {      if (L[cur] > 0 && R[cur - 1] > 0 || (!R[cur] && !L[cur + 1])) {       L[cur]--;       cur--;       cout << 0;      } else {       R[cur]--;       cur++;       cout << 1;      }     }     cout <<   n ;    }    return 0;   }