#P1931A. Recovering a Small String

Recovering a Small String

No submission language available for this problem.

Description

Nikita had a word consisting of exactly 33 lowercase Latin letters. The letters in the Latin alphabet are numbered from 11 to 2626, where the letter "a" has the index 11, and the letter "z" has the index 2626.

He encoded this word as the sum of the positions of all the characters in the alphabet. For example, the word "cat" he would encode as the integer 3+1+20=243 + 1 + 20 = 24, because the letter "c" has the index 33 in the alphabet, the letter "a" has the index 11, and the letter "t" has the index 2020.

However, this encoding turned out to be ambiguous! For example, when encoding the word "ava", the integer 1+22+1=241 + 22 + 1 = 24 is also obtained.

Determine the lexicographically smallest word of 33 letters that could have been encoded.

A string aa is lexicographically smaller than a string bb if and only if one of the following holds:

  • aa is a prefix of bb, but aba \ne b;
  • in the first position where aa and bb differ, the string aa has a letter that appears earlier in the alphabet than the corresponding letter in bb.

The first line of the input contains a single integer tt (1t1001 \le t \le 100) — the number of test cases in the test.

This is followed by the descriptions of the test cases.

The first and only line of each test case contains an integer nn (3n783 \le n \le 78) — the encoded word.

For each test case, output the lexicographically smallest three-letter word that could have been encoded on a separate line.

Input

The first line of the input contains a single integer tt (1t1001 \le t \le 100) — the number of test cases in the test.

This is followed by the descriptions of the test cases.

The first and only line of each test case contains an integer nn (3n783 \le n \le 78) — the encoded word.

Output

For each test case, output the lexicographically smallest three-letter word that could have been encoded on a separate line.

Sample Input 1

5
24
70
3
55
48

Sample Output 1

aav
rzz
aaa
czz
auz