#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
	int f = 1, x = 0;
	char ch;

	do{
		ch = getchar();
		if (ch == '-')
			f = -1;
	}while(ch < '0' || ch > '9');
	do{
		x = x * 10 + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return f * x;
}
const int N = 5e5;

int tt;
string s;
int edge[2 * N + 1][2];

int main()
{
	tt = read();

	while (tt--) {
		cin >> s;
		for (int i = 0, sum = 0; i < s.size(); i++) {
			if (s[i] == '0') {
				edge[sum + N][0]++;
				sum--;
			} else {
				edge[sum + N][1]++;
				sum++;
			}
		}
		int now = N;
		while (true) {
			if (edge[now][0] && edge[now - 1][1]) {
				putchar('0');
				edge[now][0]--;
				now--;
			} else {
				if (edge[now][1]) {
					putchar('1');
					edge[now][1]--;
					now++;
				} else {
					if (edge[now][0]) {
						putchar('0');
						edge[now][0]--;
						now--;
					} else {
						break;
					}
				}
			}
		}
		putchar('\n');
	}

	return 0;
}
