Spreadsheets

Interview

Time limit2sMemory limit512 MB

Summary

Convert a column index up to 1e9 into a base-26 name like A, Z, AA, using letters with no zero digit.

Level: Easy3 of 10
Topics: Math, String, Number theory, Implementation
Solved: No attempts yet

Problem

Petya is developing his own spreadsheet editor. His editor names columns as follows: the first 26 columns get single letters of the alphabet: A, B, C, ..., Z. Starting from column 27, columns get pairs of letters: AA, AB, ..., AZ, BA, BB, ..., BZ, ..., ZZ. Then triples of letters are used: AAA, AAB, AAC, ..., followed by strings of four letters, and so on.

Now Petya needs to get the name of a column from its number. Help him write the corresponding piece of code.

Input

The input contains several test cases. The first line holds an integer $t$ , the number of test cases ( $1 \le t \le 1000$ ).

The next $t$ lines each hold one integer $k$ ( $1 \le k \le 10^9$ ).

Output

For each test case, output the name of the $k$ -th column in the spreadsheet editor.

Examples1

Example 1
Input
```
4
1
10
100
1000
```
Expected output
```
A
J
CV
ALL
```