29782번 - 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:

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

Here 1e100 represents the integer 10ドル^{100}$. For example:

• When $i=1,ドル the program prints ABCD....XYZ.
• When $i=2,ドル the program prints AABBCC...XXYYZZ.
• When $i=3,ドル the program prints AAABBBCCC...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.

제한

• 1ドル \le \mathbf{T} \le 100$.

Test Set 1 (9점)

• 1ドル \le \mathbf{N} \le 10^6$.

Test Set 2 (20점)

• 1ドル \le \mathbf{N} \le 10^{12}$.

힌트

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