#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;

int E[N<<1],n;
char s[N];

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin>>T;
	while(T--) {
		cin>>(s+1);n=strlen(s+1);
		int sum=N;
		for(int i=1;i<=n;i++) {
			if(s[i]=='0') ++E[sum],++sum;
			else --sum,++E[sum];
		}
		int x=N;
		while(E[x-1]||E[x]) {
			if(E[x]&&(E[x]>1||!E[x-1])) --E[x],cout<<0,++x;
			else cout<<1,--x,--E[x];
		}
		cout<<'\n';
	}
	return 0;
}
