#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll INF = 1000000000000000000LL;
ll dp[123];
 
void pre()
{
	dp[1] = 1; dp[2] = 2; dp[3] = 3;
	for (int i = 4; ; ++i){
		if (INF - dp[i-1] < dp[i-3]) break;
		dp[i] = dp[i-1] + dp[i-3];
	}
}
 
void solve()
{
	ll n;
	cin >> n;
	int s[200], pos = 108;
	memset(s, 0, sizeof(s));
	while (n>0){
		if (n >= dp[pos]){
			s[pos] = 1;
			n -= dp[pos];
		}
		pos -= 1;
	}
	int fin = 199;
	while (!s[fin])--fin;
	for(int i = fin; i>0; i--)
		cout << s[i];
	cout << endl;		
}
 
int main()
{
	pre();
	int t;
	cin >> t;
	while (t--)solve();
	return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCmxsIElORiA9IDEwMDAwMDAwMDAwMDAwMDAwMDBMTDsKbGwgZHBbMTIzXTsKCnZvaWQgcHJlKCkKewoJZHBbMV0gPSAxOyBkcFsyXSA9IDI7IGRwWzNdID0gMzsKCWZvciAoaW50IGkgPSA0OyA7ICsraSl7CgkJaWYgKElORiAtIGRwW2ktMV0gPCBkcFtpLTNdKSBicmVhazsKCQlkcFtpXSA9IGRwW2ktMV0gKyBkcFtpLTNdOwoJfQp9Cgp2b2lkIHNvbHZlKCkKewoJbGwgbjsKCWNpbiA+PiBuOwoJaW50IHNbMjAwXSwgcG9zID0gMTA4OwoJbWVtc2V0KHMsIDAsIHNpemVvZihzKSk7Cgl3aGlsZSAobj4wKXsKCQlpZiAobiA+PSBkcFtwb3NdKXsKCQkJc1twb3NdID0gMTsKCQkJbiAtPSBkcFtwb3NdOwoJCX0KCQlwb3MgLT0gMTsKCX0KCWludCBmaW4gPSAxOTk7Cgl3aGlsZSAoIXNbZmluXSktLWZpbjsKCWZvcihpbnQgaSA9IGZpbjsgaT4wOyBpLS0pCgkJY291dCA8PCBzW2ldOwoJY291dCA8PCBlbmRsOwkJCn0KCmludCBtYWluKCkKewoJcHJlKCk7CglpbnQgdDsKCWNpbiA+PiB0OwoJd2hpbGUgKHQtLSlzb2x2ZSgpOwoJcmV0dXJuIDA7Cn0K

MTAKNQo2CjcKMQoyCjMKMTAKOQo4CjQ=

10
5
6
7
1
2
3
10
9
8
4