1995 年，Simon Plouffe 发现了一种针对某些常数的特殊求和方式。两年后，随着 Bailey 和 Borwein 发表的论文，这种求和方式被命名为 Bailey-Borwein-Plouffe 公式。与此同时，一个轰动性的公式出现了，即：

$$\pi = \sum_{k=0}^{\infty} \frac{1}{16^k} \left( \frac{4}{8k+1} - \frac{2}{8k+4} - \frac{1}{8k+5} - \frac{1}{8k+6} \right)$$

几个世纪以来，人们一直认为如果不计算前 $n-1$ 位数字，就无法计算 $\pi$ 的第 $n$ 位数字，但该公式的发现提供了这种可能性。本题要求你计算 $\pi$ 在十六进制小数点后的第 $n$ 位十六进制数字。例如，$\pi$ 的十六进制形式为 $3.243F6A8885A308D313198A2E \dots$，其中第 1 位是 2，第 11 位是 A，第 15 位是 D。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 32$)，表示测试用例的总数。 接下来的每一行包含一个整数 $n$ ($1 \le n \le 100000$)。

输出格式

对于每个测试用例，输出一行，以测试用例的编号开头。然后输出整数 $n$，以及对应的答案，答案应为 $\{0, 1, \dots, 9, A, B, C, D, E, F\}$ 中的一个十六进制字符。

样例

样例输入 1

5
1
11
111
1111
11111

样例输出 1

Case #1: 1 2
Case #2: 11 A
Case #3: 111 D
Case #4: 1111 A
Case #5: 11111 E