题目描述

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 \cdots$，其第 $1$ 位数字是 $2$，第 $11$ 位是 $A$，第 $15$ 位是 $D$。

输入格式

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

输出格式

对于每个测试用例，输出一行，以测试用例的标识（形如 Case #x:）开头，随后输出整数 $n$，以及所求的答案，答案应为 $\{0, 1, \dots, 9, A, B, C, D, E, F\}$ 中的一个十六进制字符。

5
1
11
111
1111
11111

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

提示

翻译由 DeepSeek V3.2 完成