“0/1 字符串” 字 符 串 是一个字符串，其中每个字符都是 0 或 1 。有两个操作可以在 0/1 字符串上执行：
switch ：把 1 都变为 0 ， 0 都变为 1 。例如， 100 变为 011 。
reverse ：字符串反转。 例如， 100 变为 001 。 考虑这个 0/1 字符串的无限序列：
S0=“” S1=“0” S2=“001” S3=“0010011” S4=“001001100011011” …
S_N=S_{N−1}+“0”+switch(reverse(S_{N−1}))
请你求出 S_{googol} 中的第 K 个字符，其中 googol=10^{100} 。
第一行包含整数 T ，表示共有 T 组测试数据。
每组数据占一行，包含一个整数 K 。
每组数据输出一个结果，每个结果占一行。
结果表示为 Case # x : y ，其中 x 是组别编号（从 1 开始）， y 是 S_{googol} 中的第 K 个字符（从1开始）。
输入样例：
4 1 2 3 10
输出样例：
Case #1: 0 Case #2: 0 Case #3: 1 Case #4: 0
1≤T≤100 , 1≤K≤10^{18}