#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
void sol(string& a,int flag,int& len,deque<int>& q){
	if(flag){
		while(!q.empty()&&!q.back()){
			a+=(char)('0'+q.back());
			q.pop_back();
			len--;
		}
	}else {
		while(!q.empty()&&!q.front()){
			a+=(char)('0'+q.front());
			q.pop_front();
			len--;
		}		
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		string s;
		cin>>s;
		string ans="";
		int flag=0,len=0;//判断是偶数还是技术
		deque<int>q;
		for(int i=0;s[i];i++){
			if(len==0&&(s[i]=='0')){
				len=0;
				ans+="0";
				continue;
			}
			if((len&1)==0&&(s[i]=='0')){
				ans+="0";
				flag^=1;
				sol(s,flag,len,q);
				continue;
			}//那么就是变成了奇数反转
			if((len&1)==1&&(s[i]=='0')){
				if(!flag){
					q.push_back(0);
				}else {
					q.push_front(0);
				}
				len++;//没有进行翻转
				continue;
			}
			if(s[i]=='1'){
				if(!flag){
					q.push_back(1);
				}else {
					q.push_front(1);
				}
				len++;//没有进行翻转		
				continue;		
			}
		}
		while(!q.empty()){
			int cnt0=0,cnt1=0;
			while(!q.empty()){
				if(q.back()){
					cnt1++;
				}else {
					cnt0++;
				}
				q.pop_back();
			}
			for(int i=1;i<=cnt0;i++){
				ans+="10";
			}
			for(int i=1;i<=(cnt1-cnt0);i++){
				ans+="1";
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}