#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int t; cin.tie(nullptr)->sync_with_stdio(false), cin >> t;
	while (t--) {
		string S; 
		cin >> S;
		int N = S.size();
		__int128 X = 0;
		for (int i = 0; i < N; ++i)
			if (X <<= 1, S[i] == '1')
				X |= 1;
		string ans;
		if (X == 0)
			ans = "0";
		else {
			while (X > 0)
				ans += char('0'+X%6), X /= 6;
			reverse(ans.begin(),ans.end()); }
		cout << ans << '\n'; }
	return 0; }
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCWludCB0OyBjaW4udGllKG51bGxwdHIpLT5zeW5jX3dpdGhfc3RkaW8oZmFsc2UpLCBjaW4gPj4gdDsKCXdoaWxlICh0LS0pIHsKCQlzdHJpbmcgUzsgCgkJY2luID4+IFM7CgkJaW50IE4gPSBTLnNpemUoKTsKCQlfX2ludDEyOCBYID0gMDsKCQlmb3IgKGludCBpID0gMDsgaSA8IE47ICsraSkKCQkJaWYgKFggPDw9IDEsIFNbaV0gPT0gJzEnKQoJCQkJWCB8PSAxOwoJCXN0cmluZyBhbnM7CgkJaWYgKFggPT0gMCkKCQkJYW5zID0gIjAiOwoJCWVsc2UgewoJCQl3aGlsZSAoWCA+IDApCgkJCQlhbnMgKz0gY2hhcignMCcrWCU2KSwgWCAvPSA2OwoJCQlyZXZlcnNlKGFucy5iZWdpbigpLGFucy5lbmQoKSk7IH0KCQljb3V0IDw8IGFucyA8PCAnXG4nOyB9CglyZXR1cm4gMDsgfQoJ

NAoxMTEKMTAwMAoxMDExMTAxMDExMTAxCjExMTAxMTEwMTEwMTAxMDExMTAx

4
111
1000
1011101011101
11101110110101011101