[U] Unraveling the History

고려 시대의 학자 하의비는 최근 들어온 제자 바의히에게 활자의 역사를 가르치기로 했다. 이를 위해 목판 활자를 사용한 신라 시대의 기록을 연구하던 하의비는 놀라운 사실을 알아냈다. 바로 신라 시대의 사람들은 목판 활자를 사용하여 영어 알파벳 대문자로 구성된 문자열을 찍어냈다는 점과, 이를 숨기기 위해 이와 관련된 모든 기록을 암호화했다는 점이다!

하의비의 연구에 따르면 신라 시대의 학자들은 $T+26$개의 활자 문자열을 가지고 있으며, 알파벳 대문자 하나로 이루어진 기초 활자 문자열 $26$개와 학자들이 만든 $T$개의 복합 활자 문자열로 이루어져 있다. 기초 활자 문자열에는 A부터 Z까지 각각 $1$부터 $26$까지의 번호가 붙어있으며, 복합 활자 문자열에는 만든 순서대로 $1$부터 $T$까지의 번호가 매겨져 있다.

$t$번 복합 활자 문자열은 기초 활자 문자열과 이전에 만든 복합 활자 문자열을 총 $N\_t$개 이어 붙여서 만들어지며, 이를 만드는 과정을 암호화한 수 $C\_t$는 다음과 같이 만들어진다.

1. 수열 $A$를 만든다. 초기에 이 수열은 비어 있다.

2. $t$번 복합 활자 문자열의 끝에 활자 문자열을 하나씩 추가한다. 이때 수열 $A$에는 다음과 같이 원소를 추가한다.

   • 만약 추가한 활자 문자열이 $i$번 기초 활자 문자열이라면, $A$의 끝에 $i$를 추가한다. $(1 \le i \le 26)$
   • 만약 추가한 활자 문자열이 $i$번 복합 활자 문자열이라면, $A$의 끝에 $-i$를 추가한다. $(1 \le i < t)$

3. $A$를 $26+t$진법으로 읽어서 $C\_t$를 만든다. 정확히는, $C\_t = \sum\_{k=1}^{N\_t}(26+t)^{N\_t-k}A\_{k}$이다.

$T$개의 암호화된 복합 활자 문자열이 주어질 때, 하의비의 연구에 따라 $T$개의 복합 활자 문자열을 모두 해독해 보자.

첫째 줄에는 알아내야 하는 복합 활자 문자열의 수 $T$가 주어진다. $(1\le T\le 1\\, 000\\, 000)$

둘째 줄부터 $T$개의 줄에 걸쳐, $t+1$번째 줄에는 주어진 방법대로 암호화된 $t$번 복합 활자 문자열을 의미하는 정수 $C\_t$가 주어진다. $(1\le |C\_t|\le 10^{18})$

첫째 줄부터 $T$개의 줄에 걸쳐, $t$번째 줄에는 $t$번 복합 활자 문자열을 출력한다.

$T$개의 활자 문자열의 길이의 합이 $1\\,000\\,000$을 넘지 않음이 보장된다.