P16502 [GKS 2015 #A] Googol String

一个“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$ 个字符。

### 限制 $1 \le T \le 100$。 **小数据集（测试集 1 - 可见）** $1 \le K \le 10^5$。 **大数据集（测试集 2 - 隐藏）** $1 \le K \le 10^{18}$。 翻译由 DeepSeek V4 Pro 完成