3. Zoraď všetky slová, vypíš n-té

Vlejdovi sa veľmi zapáčila úloha Zwarte doos z minulej série. Hneď vyriešil všetkých desať hlavolamov. Bohužiaľ, potrvá celkom dlho kým zwarte doos načerpá novú inšpiráciu a vymyslí nové hlavolamy. Preto sa Vlejd od nudy začal zamýšľať, ako taká zwarte doos funguje. Najviac sa mu zapáčil šiesty level z prvej série. Zistil, že krabička vie celkom rýchlo odpovedať aj keď do nej hodí veľmi veľké číslo. Rozhodol sa, že si to vyskúša naprogramovať.

Úloha

Predstavte si, že zoberiete všetkých 26 veľkých písmen anglickej abecedy a poskladáte z nich všetky možné slová. Tieto slová potom zoradíte. Najskôr podľa dĺžky a potom podľa abecedy. Takto získate postupnosť, ktorej prvky vám vracala šiesta krabička. Prvé slovo je A a za ním nasledujú B, C, …, Z, AA, AB, AC, AZ, BA, …, ZZ, AAA, …

Vašou úlohou bude urobiť program, ktorý na vstupe dostane číslo \(n\) a vypíše \(n\)-té slovo vyššie spomenutej postupnosti. Pre \(1\) má teda vypísať A, pre \(28\) AB …

Vstup

Na prvom riadku vstupu je \(1 \leq t \leq 10\,000\) – počet otázok pre krabičku. V každom z nasledujúcich \(t\) riadkov sa nachádza číslo \(1 \leq n \leq 10^{15}\).

Výstup

Pre každú otázku vypíšte \(n\)-té slovo postupnosti.

Príklady

Input:

5
2
1
4961867752
47
7946

Output:

B
A
PAPAGAJ
AU
KSP