#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char c[500010];
int hh[1000010];
int T;
int main(){
	cin>>T;
	while(T--){
		scanf("%s",c+1);
		int len=strlen(c+1);
		int now=len;
		for(int i=1;i<=len;i++){
			if(c[i]=='1')hh[now++]++;
			else hh[--now]++;
		}
		now=len;
		for(int i=1;i<=len;i++){
			if(hh[now-1]&&(!hh[now]||hh[now-1]>1))printf("0"),hh[--now]--;
			else printf("1"),hh[now++]--;
		}
		printf("\n");
	}
}