Problem: You are given a string s of 0's and 1's. You are allowed to perform the following operation:

  * choose a non-empty contiguous substring of s that contains an equal number of 0's and 1's;
  * flip all characters in the substring, that is, replace all 0's with 1's, and vice versa;
  * reverse the substring. 



For example, consider s = 00111011, and the following operation:

  * Choose the first six characters as the substring to act upon: 00111011. Note that the number of 0's and 1's are equal, so this is a legal choice. Choosing substrings 0, 110, or the entire string would not be possible.
  * Flip all characters in the substring: 11000111.
  * Reverse the substring: 10001111. 



Find the lexicographically smallest string that can be obtained from s after zero or more operations.

Input

The first line contains a single integer T (1 ≤ T ≤ 5 ⋅ 10^5) — the number of test cases. Each of the following T lines contains a single non-empty string — the input string s for the respective test case.

All strings consist of characters 0 and 1, and their total length does not exceed 5 ⋅ 10^5.

Output

For each test case, on a separate line print the lexicographically smallest string that can be obtained from s after zero or more operations.

Example

Input


3
100101
1100011
10101010


Output


010110
0110110
10101010

Note

In the first test case a single operation should be applied to the entire string.

In the second test case two operations are needed: 0111001, 0110110.

In the third test case the string stays the same after any operation.

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+100;
#define fr(i,a,b) for(int i = a;i <= b; ++i)
#define nfr(i,a,b) for(int i = a;i >= b; --i)

int rt;
struct fhq_treap{
   int val[N],rnd[N],ch[N][2],tot,siz[N];
   int sum[N],tag[N];
   int premax[N],premin[N],pre[N];
   inline int new_node(){
      ++tot;
      tag[tot] = sum[tot] = pre[tot] = 0;
      siz[tot] = 1;
      rnd[tot] = rand(); ch[tot][0] = ch[tot][1] = 0;
      premax[tot] = premin[tot] = val[tot] = 0;
      return tot;
   }
   inline void init(){
      premax[0] = 0; premin[0] = 0; sum[0] = 0;
      tot = 0; rt = 0;
   }
   #define lc ch[x][0]
   #define rc ch[x][1]
   void push_up(int x){
      siz[x] = siz[ch[x][0]]+siz[ch[x][1]]+1;
      sum[x] = sum[ch[x][0]]+sum[ch[x][1]]+val[x];
      pre[x] = sum[ch[x][0]]+val[x];
      premax[x] = max(pre[x],max(premax[ch[x][0]],pre[x]+premax[ch[x][1]]));
      premin[x] = min(pre[x],min(premin[ch[x][0]],pre[x]+premin[ch[x][1]]));
   }
   void push_down(int x){
      if(tag[x]){
         tag[lc] ^= 1; tag[rc] ^= 1;
         val[lc] = -val[lc]; val[rc] = -val[rc];
         sum[lc] = -sum[lc]; sum[rc] = -sum[rc];
         pre[lc] = sum[lc]+pre[lc]+val[lc]; pre[rc] = sum[rc]+pre[rc]+val[rc];
         premax[lc] = sum[lc]+premax[lc]; premin[lc] = sum[lc]+premin[lc];
         premax[rc] = sum[rc]+premax[rc]; premin[rc] = sum[rc]+premin[rc];
         swap(lc,rc);
         tag[x] = 0;
      }
      return ;
   }
   void operate(int x){
      tag[x] ^= 1;
      val[x] *= -1; sum[x] = -sum[x];
      pre[x] = sum[x]+pre[x]+val[x];
      premax[x] = sum[x]+premax[x]; premin[x] = sum[x]+premin[x];
      return ;
   }
   inline int merge(int x,int y){
      if(!x || !y)return x+y;
      if(rnd[x] < rnd[y]){
         push_down(x);
         ch[x][1] = merge(ch[x][1],y); push_up(x);
         return x;
      } else {
         push_down(y);
         ch[y][0] = merge(x,ch[y][0]); push_up(y);
         return y;
      }
   }
   inline void split_siz(int cur,int k,int &x,int &y){
      if(!cur){
         x = y = 0; return ;
      }
      push_down(cur);
      if(siz[ch[cur][0]]+1 <= k){
         x = cur; split_siz(ch[cur][1],k-siz[ch[cur][0]]-1,ch[x][1],y);
      } else {
         y = cur; split_siz(ch[cur][0],k,x,ch[y][0]);
      }
      push_up(cur);
   }
   inline void insert_right(int curv){
      int x = new_node();
      val[x] = curv; push_up(x);
      rt = merge(rt,x);
   }
   inline int query_sum(int l,int r){
      int x,y,z;
      split_siz(rt,l-1,x,y);
      split_siz(y,r-l+1,y,z);
      int ret = sum[y];
      rt = merge(merge(x,y),z);
      return ret;
   }
   inline void reverse(int l,int r){
      int x,y,z;
      split_siz(rt,l-1,x,y);
      split_siz(y,r-l+1,y,z);
      operate(y);
      rt = merge(merge(x,y),z);
   }
   inline void dfs(int x,int rk){
      push_down(x);
      if(ch[x][0])dfs(ch[x][0],rk);
      if(ch[x][1])dfs(ch[x][1],rk+siz[ch[x][0]]+1);
      //cerr << x <<' ' << ch[x][0] <<' ' << ch[x][1] << endl;
      printf("%d pre: %d premax %d premin %d\n",x,pre[x],premax[x],premin[x]);
      return ;
   }
   inline void search(int l){
      int x,y,z;
      split_siz(rt,l-1,x,y);
   //   if(l == 4)dfs(y,0);
      z = y; int rk = 1,csum = 0;
      while(1){
         push_down(z);
         if(ch[z][0] && csum+premin[ch[z][0]] < 0)z = ch[z][0];
         else if(!ch[z][1] || csum+pre[z] < 0){
            rk += siz[ch[z][0]]; csum += pre[z]; break;
         } else csum += pre[z],rk += siz[ch[z][0]]+1,z = ch[z][1];
      }
      //cerr << l <<' ' << rk <<' ' << csum << endl;
      if(csum >= 0){
         rt = merge(x,y); return ;
      }
      int w;
      split_siz(y,rk,y,w);
      z = w; rk = 1;
      while(1){
         push_down(z);
         if(ch[z][0] && csum+premax[ch[z][0]] >= 0)z = ch[z][0];
         else if(!ch[z][1] || csum+pre[z] >= 0){
            rk += siz[ch[z][0]]; csum += pre[z]; break;
         } else csum += pre[z],rk += siz[ch[z][0]]+1,z = ch[z][1];
      }
      if(csum < 0){
         rt = merge(x,merge(y,w));
         return ;
      }
      rk += siz[y];
      //cerr << l <<' ' << rk << ' ' << csum << "max\n";
      rt = merge(y,w);
      split_siz(rt,rk,y,w); operate(y);
      rt = merge(merge(x,y),w);
      return ;
   }
}t;


char s[N];
void solve(){
   scanf("%s",s+1);
   int n = strlen(s+1);
   t.init();

   fr(i,1,n)t.insert_right((s[i]-'0' == 1) ? 1 : -1);

   fr(i,1,n){
      if(t.query_sum(i,i) == -1)continue ;
      t.search(i);
   }
//   t.dfs(rt,0);
   fr(i,1,n)printf("%c",t.query_sum(i,i) == -1 ? '0' : '1');
   puts("");
}

int main(){
   #ifndef ONLINE_JUDGE
         freopen("1458D.in","r",stdin);
      //freopen("1458D.out","w",stdout);
   #endif
   int t; scanf("%d",&t);
   while(t--)solve();
   return 0;
}