P12949 [GCJ Farewell Round #1] ASCII Art

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: ```python 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.

**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}$.