/*---Author:HenryHuang---*/
/*---Never Settle---*/
#include<bits/stdc++.h>
#define bias 500000
using namespace std;
const int maxn=1e6+5;
char s[maxn];
int nex[maxn][2];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--){
		cin>>(s+1);int lens=strlen(s+1);
		int now=0;
		for(int i=1;i<=lens;++i){
			++nex[now+bias][s[i]-'0'];
			if(s[i]=='0') --now;
			else ++now;
		}
		now=0;
		for(int i=1;i<=lens;++i){
			if(nex[now+bias][0]&&nex[now+bias-1][1]) --nex[now+bias][0],--now,cout<<"0";
			else if(nex[now+bias][1]) --nex[now+bias][1],++now,cout<<"1";
			else --nex[now+bias][0],--now,cout<<"0";
		}
		cout<<'\n';
	}
	return 0;
}