ASCII 아트

면접 대비

시간 제한20초메모리 제한1024 MB

요약

정수 N이 주어질 때, 라운드 i마다 A부터 Z까지 각 글자를 i번씩 출력하는 프로그램에서 N번째로 출력되는 글자를 구합니다.

문제

Cody-Jamal은 생성형 인공지능이 그림을 만들어 낸다는 이야기를 들었다. 새로운 예술의 가능성에 설레지만, 사람이 만든 예술이 밀려날까 걱정하고 있다. 그래서 사람이 만들 수 없는 예술을 컴퓨터로 만드는 것이 좋은 절충안이라고 생각했다.

Cody-Jamal은 컴퓨터 생성 아트를 이제 막 시작했기 때문에 간단한 것부터 만들기로 했다. 그는 영문 알파벳을 두 번씩 반복해 보여 주는 아주 긴 문자열을 만들려고 한다. 알파벳이 어디에나 있고 영원히 이어진다는 뜻을 담으려는 것이다.

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

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

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

물론 Cody-Jamal의 프로그램이 끝나는 데는 아주 오랜 시간이 걸린다. 출력될 때까지 기다리지 않고 N번째로 출력되는 글자가 무엇인지 알려 줄 수 있겠는가?

첫 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 $N$ 이 한 줄에 주어진다.

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

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