11121

#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <cstdlib>

#define INF 1000000
#define ll long long

using namespace std;

int main()
{
	int t,kase=1;
	ll n;
	int a=-2,b=-3;
	//cout<<a%2<<" "<<b%2<<"\n";
	string str;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld",&n);
		if(n==0)
		{
			printf("Case #%d: ",kase++);
			printf("0\n");
			continue;
		}
		str="";
		while(n)
		{
			if(n%2)
			{
				//cout<<"got\n";
				str.append(1u,'1');
				n -= 1;n/=(-2);
			}
			else
			{
				n/=(-2);
				//if(str.size())
				str.append(1u,'0');
			}
		}
		printf("Case #%d: ",kase++);
		for(int i=str.size()-1;i>=0;i--)
		printf("%c",str[i]);
		printf("\n");
	}
	return 0;
}