“$0/1$ 字符串”是一个字符串，其中每个字符都是 $0$ 或 $1$。

有两个操作可以在 $0/1$ 字符串上执行：

• switch：把 $1$ 都变为 $0$，$0$ 都变为 $1$。例如，100 变为 011。
• reverse：字符串反转。 例如，100 变为 001。

考虑这个 $0/1$ 字符串的无限序列：

$S\_0 = “”$

$S\_1 = “0”$

$S\_2 = “001”$

$S\_3 = “0010011”$

$S\_4 = “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 \le T \le 100$,

$1 \le K \le 10^{18}$

Samples

4
1
2
3
10

Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0