ASCII 예술

Cody-Jamal은 생성형 인공지능이 예술 작품을 만든다는 이야기를 들었다. 그는 새로운 예술의 가능성에 기대하면서도 인간이 만든 예술이 밀려날까 봐 걱정한다. 그는 인간이 도저히 만들 수 없는 예술을 컴퓨터로 만들면 좋은 절충안이 될 것이라고 생각했다.

Cody-Jamal은 컴퓨터 생성 예술을 이제 막 시작했으므로 간단한 것부터 시작했다. 그는 영어 알파벳의 보편성과 영속성을 나타내기 위해, 영어 알파벳을 이중으로 반복되는 방식으로 보여 주는 거대한 문자열을 만들고자 한다.

Cody-Jamal은 다음 프로그램을 작성했다.

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

여기서 1e100는 정수 $10^{100}$을 나타낸다. 예를 들면 다음과 같다.

• $i=1$일 때 프로그램은 ABCD....XYZ를 출력한다.

• $i=2$일 때 프로그램은 AABBCC...XXYYZZ를 출력한다.

• $i=3$일 때 프로그램은 AAABBBCCC...XXXYYYZZZ를 출력한다.

물론 Cody-Jamal의 프로그램이 끝나려면 오랜 시간이 걸린다. 해당 글자가 출력될 때까지 기다리지 않고 $\mathbf{N}$-번째로 출력되는 글자가 무엇인지 알아내도록 도와줄 수 있는가?

제한

시간 제한: 20초. 메모리 제한: 2 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1 (결과 공개)

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

테스트 세트 2 (결과 공개)

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

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 $\mathbf{N}$ 하나가 주어지는 한 줄로 이루어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$은 (1부터 시작하는) 테스트 케이스 번호이고, $y$는 Cody-Jamal의 프로그램이 $\mathbf{N}$-번째로 출력하는 문자이다.

Cody-Jamal의 프로그램이 처음 출력하는 $35$개의 글자는 ABCDEFGHIJKLMNOPQRSTUVWXYZAABBCCDDE...이다. 따라서 $5$번째로 출력되는 문자는 E이고, $31$번째로 출력되는 문자는 C이다.