#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
int cnt[maxn*2];
void work(){
	string s;
	cin>>s;
	int n=s.size();
	s=" "+s;
	for(int i=0;i<=2*n;i++){
		cnt[i]=0;
	}int now=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='0')cnt[n+now-1]++,now--;
		else cnt[n+now]++,now++;
	}now=0;
	for(int i=1;i<=n;i++){
		if(cnt[n+now-1]&&(cnt[n+now-1]>1||!cnt[n+now]))printf("0"),cnt[n+now-1]--,now--;
		else printf("1"),cnt[n+now]--,now++;
	}puts("");
	return ;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)work();
}