题目描述

一个“0/1 字符串”是指每个字符都是 0 或 1 的字符串。在一个 0/1 字符串上可以进行两种操作：

• 切换：每个 0 变成 1，每个 1 变成 0。例如，“100” 变成 “011”。
• 反转：将字符串倒转。例如，“100” 变成 “001”。

考虑如下无穷的 0/1 字符串序列：

$S_0 = ``"$

$S_1 = ``0"$

$S_2 = ``001"$

$S_3 = ``0010011"$

$S_4 = ``001001100011011"$

...

$S_N = S_{N-1} + ``0" + \text{\textbf{切换}}(\text{\textbf{反转}}(S_{N-1}))$.

你需要求出 $S_{\text{googol}}$ 的第 $K$ 个字符，其中 googol = $10^{100}$。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来的 $T$ 行，每行包含一个整数 $K$。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 $S_{\text{googol}}$ 的第 $K$ 个字符。

4
1
2
3
10

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

提示

限制

$1 \le T \le 100$。

小数据集（测试集 1 - 可见）

$1 \le K \le 10^5$。

大数据集（测试集 2 - 隐藏）

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

翻译由 DeepSeek V4 Pro 完成