题目描述

33DAI 的表格软件用字母给每一列编号：第 $1$ 列叫 A，第 $2$ 列叫 B，……，第 $26$ 列叫 Z，第 $27$ 列叫 AA，第 $28$ 列叫 AB。

编号的规律是：把只由大写英文字母组成的列名按长度从小到大排列，长度相同的按字典序排列，排在第 $n$ 个的列名就是第 $n$ 列的编号。例如：

给定 $t$ 个列号，33DAI 想知道它们各自的列名。

输入格式

从标准输入读入数据。

输入的第一行是一个整数 $t$（$1 \le t \le 10^5$），表示列号的个数。

接下来 $t$ 行，每行一个整数 $n$（$1 \le n \le 10^{12}$），表示一个列号。

输出格式

输出到标准输出。

输出 $t$ 行，顺序与输入一致。每行一个只由大写英文字母组成的字符串，表示该列号对应的列名。

6
1
26
27
52
53
702

A
Z
AA
AZ
BA
ZZ

4
703
675
676
18278

AAA
YY
YZ
ZZZ

1
1000000000000

DTMCHRXUN

样例解释

• 样例 1：一位的列名一共 $26$ 个（A 到 Z），所以第 $27$ 个进入两位；两位的列名一共 $26 \times 26 = 676$ 个，第 $52$ 个是两位里的第 $52 - 26 = 26$ 个，即 AZ；第 $53$ 个是两位里的第 $27$ 个，即 BA；第 $702$ 个是两位里的最后一个，即 ZZ。
• 样例 2：三位从第 $703$ 个开始，第一个是 AAA；$n = 675$ 是两位里的第 $675 - 26 = 649$ 个，即 YY；$n = 676$ 是两位里的第 $650$ 个，即 YZ；两位一共有 $676$ 个，所以第 $702$ 个是 ZZ，第 $18278$ 个是三位里的最后一个 ZZZ（$26 + 676 + 17576 = 18278$）。
• 样例 3：第 $10^{12}$ 个列名的长度是 $9$，答案是 DTMCHRXUN。

提示

• 列号最大到 $10^{12}$，读入与计算请使用 $64$ 位整型。
• 每行只输出一个大写字母串，不要输出多余的空格。

数据范围

对于所有测试数据，保证 $1 \le t \le 10^5$，$1 \le n \le 10^{12}$。

共 $15$ 个测试点，按测试点计分：子任务 $1$、$2$ 的每个测试点 $6$ 分，子任务 $3$ 的每个测试点 $8$ 分。