题目描述

Cody-Jamal has heard about generative artificial intelligence producing art. He is excited about the new art opportunities, but also worried about human-created art being displaced. He thought a good compromise would be to use computers to create art that humans simply cannot.

Since Cody-Jamal is just beginning at computer-generated art, he started simple. He wants to create an immense string that shows the English alphabet in a doubly-repeated way, to represent its ubiquity and permanence.

Cody-Jamal wrote the following program:

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

Here $1 \mathrm{e} 100$ represents the integer $10^{100}$. For example:

• When $i=1$, the program prints $\mathrm{ABCD} \ldots . . \mathrm{XYZ}$.
• When $i=2$, the program prints $\mathrm{AABBCC} \ldots \mathrm{XXYYZZ}$.
• When $i=3$, the program prints $\mathrm{AAABBBCCC} \ldots \mathrm{XXXYYYZZZ}$.

Of course, Cody-Jamal's program takes a long time to finish. Can you help him know what the $\mathbf{N}$-th printed letter will be without waiting for it to be printed?

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each test case consists of a single line with an integer $\mathbf{N}$.

输出格式

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the $\mathbf{N}$-th character printed by Cody-Jamal's program.

2
5
31

Case #1: E
Case #2: C

提示

Sample Explanation

The first 35 letters printed by Cody-Jamal's program are ABCDEFGHIJKLMNOPQRSTUVWXYZAABBCCDDE… Therefore, the 5th printed character is E and the 31st is C.

Limits

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

Test Set 1 (9 Pts, Visible Verdict)

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

Test Set 2 (20 Pts, Visible Verdict)

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