#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
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;
				if(flag){
					while(!q.empty()&&!q.back()){
						ans+=(char)('0'+q.back());
						q.pop_back();
						len--;
					}
				}else {
					while(!q.empty()&&!q.front()){
						ans+=(char)('0'+q.front());
						q.pop_front();
						len--;
					}		
				}
				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;
}