#include <iostream>
#include <vector>

using namespace std;

void Vyres(long long int zbytek)
{
	if(zbytek == 0)
	{
		cout << '0' << endl;
		return;
	}

	// Sem budeme přidávat bity výsledného čísla v -2 soustavě
	vector<char> kod;

	while(zbytek != 0)
	{
		// Pokud je zbytek lichý, zapíšeme 1, jinak 0
		if(abs(zbytek) % 2 == 1)
		{
			kod.push_back('1');

			// První bit (hodnoty jedna) jsme nastavili na jedna, zbytek tedy
			// musí mít celkovou hodnotu o jedna menší.
			zbytek = zbytek - 1;
		}
		else
		{
			kod.push_back('0');
		}

		// Ostatní bity výsledku nalezneme tak, že stejný postup opakujeme
		// pro zbytek posunutý o jednu mocninu -2 doprava, tedy zbytek / -2
		zbytek = zbytek / -2;
	}

	// Pozpátku (tedy od v absolutní hodnotě největšího) vypíšeme bity výsledku
	for(int i = kod.size() - 1; i >= 0; i--)
	{
		cout << kod[i];
	}

	cout << endl;
}

int main()
{
	int k;

	cin >> k;

	for(int i = 0; i < k; i++)
	{
		long long int r;
		cin >> r;
		Vyres(r);
	}

	return 0;
}