Description

Cody-Jamal 听说了生成式人工智能创作艺术的事情。他对这种新的艺术创作方式感到兴奋，但同时也担心人类创作的艺术会被取代。他认为一个很好的折衷方案是利用计算机来创作人类无法完成的艺术作品。

由于 Cody-Jamal 刚刚开始接触计算机生成艺术，他决定从简单的开始。他想创建一个巨大的字符串，以双重重复的方式展示英文字母，以表现字母的普遍性和永恒性。

Cody-Jamal 编写了以下程序：

for i = 1 to 1e100:
    for letter = A to Z:
        print letter i times

这里 $1 \mathrm{e} 100$ 表示整数 $10^{100}$。例如：

• 当 $i=1$ 时，程序会输出 $\mathrm{ABCDEFGHIJKLMNOPQRSTUVWXYZ}$（26 个字母各出现 1 次）
• 当 $i=2$ 时，程序会输出 $\mathrm{AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ}$（26 个字母各出现 2 次）
• 当 $i=3$ 时，程序会输出 $\mathrm{AAABBBCCCDDDEEEFFFGGGHHHIIIJJJKKKLLLMMMNNNOOOPPPQQQRRRSSSTTTUUUVVVWWWXXXYYYZZZ}$（26 个字母各出现 3 次）

显然，Cody-Jamal 的这个程序需要运行极其漫长的时间。你能在不实际运行程序的情况下，直接计算出程序输出的第 $\mathbf{N}$ 个字符是什么吗？

Input Format

输入的第一行给出测试用例的数量 $\mathbf{T}$（$1 \leq \mathbf{T} \leq 100$）。随后是 $\mathbf{T}$ 个测试用例，每个测试用例单独占一行，包含一个整数 $\mathbf{N}$（$1 \leq \mathbf{N} \leq 10^{12}$）。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是程序输出的第 $\mathbf{N}$ 个字母（大写）。

2
5
31

Case #1: E
Case #2: C

Hint

程序输出的字符序列开始部分为：

• $i=1$: A(1), B(2), C(3), D(4), E(5),..., Z(26)
• $i=2$: A(27-28), B(29-30), C(31-32),..., Z(78)
• ...

因此：

• 第 5 个字符是 E
• 第 31 个字符是 C（位于第二轮的 C 部分）

数据范围

• $1 \leq \mathbf{T} \leq 100$

测试集 1（9 分，可见判定）

• $1 \leq \mathbf{N} \leq 10^{6}$

测试集 2（20 分，可见判定）

• $1 \leq \mathbf{N} \leq 10^{12}$

翻译由 DeepSeek V3 完成