#include<cstring>
#include<cstdio>
int T;
int v[1000005],t[1000005];
char c[500005];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",c);
		int n=strlen(c),s=500002,num=0;
		for(int i=0;i<n;++i)
			if(c[i]=='0')
			{
				if(t[s]!=T)t[s]=T,v[s]=1;
				else ++v[s];
				if(s>500002)++num;
				--s;
			}
			else
			{
				++s;
				if(t[s]!=T)t[s]=T,v[s]=1;
				else ++v[s];
				if(s>500002)++num;
			}
		s=500002;
		while((t[s]==T&&v[s])||(t[s+1]==T&&v[s+1]))
			if(t[s]==T&&v[s]&&(v[s]>1||!num))
				num+=--v[s--],putchar('0');
			else
				num-=v[++s]--,putchar('1');
		putchar('\n');
	}
}