F. Palindromicity
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Output any string of lowercase English letters with length at most $$$300$$$ that has exactly $$$n$$$ palindromic substrings.

Recall that $$$p$$$ is a substring of $$$q$$$ if $$$p$$$ can be obtained by removing several characters (possibly none) from the beginning and from the end of $$$q$$$. Also recall that a palindrome is a string that reads the same backwards as forwards. For example, aba and o are palindromes, but ab and aaba are not.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^3$$$) — the number of test cases.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^4$$$).

Output

For each test case, output one string of lowercase English letters with length at most $$$300$$$ that has exactly $$$n$$$ palindromic substrings.

We have a proof that, under the given constraints, such a string always exists.

Example
Input
6
1
11
12
13
21
25
Output
o
kannawoah
abacaba
feelssadman
howtomakegoodsamples
anutforajaroftuna