1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem: Base -2 (11121)
* @author Christian Mitterreiter
* @author Rolf Luigs
* @version 1.0, 05/12/2009
* Status : Accepted
* Runtime: 2.956
*/


import java.util.Scanner;

public class Main {


public static void base2(long n) {

double n1 = (double)n / -2.0;
int rest;
n = (int) Math.ceil(n1);

if (n == n1) { //Wenn n "restlos" durch -2 teilbar war, stimen n1 und die aufgerundete Zahl n überein.
rest = 0; //Rest 0
}
else { //War ein restloses Teilen nicht möglich, entstand durch das Aufrunden eine von n1
//verschiedene Zahl: Rest vorhanden
rest = 1; //Rest 1
}

if (n!=0) { //solange n nicht 0 ist, wird die Basisberechnung ein weiteres Mal aufgerufen
base2(n);
}

System.out.printf("%d", rest);
}


public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

long N, count;
long n;
count = 1;
N = sc.nextLong(); //Anzahl der Testfälle

while (N>0) {
N--;
n =sc.nextLong(); //Einlesen der umzuwandelden Zahl
System.out.printf("Case #%d: ", count);
base2(n); //Basisberechnung
System.out.printf("\n");
count ++;
}
}
}