G. Median Solve Order
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The students at Rubgers University are organizing a programming contest. Since a lot of strong teams will participate, they expect some of them to solve all problems. To distinguish between them, a special prize will be awarded to the team with a special solve order.

The contest consists of $$$N \leq 26$$$ problems labelled $$$\mathrm{A}$$$, $$$\mathrm{B}$$$, etc: the first $$$N$$$ letters of the English alphabet.

A solve order for a team is a sequence of letters denoting the order in which it solved all the problems: e.g., for $$$N=3$$$, a possible solve order is $$$\mathrm{BAC}$$$ — $$$\mathrm{B}$$$ solved first, then $$$\mathrm{A}$$$, then $$$\mathrm{C}$$$. We only consider teams which solve every problem exactly once, so, e.g., $$$\mathrm{AC}$$$ or $$$\mathrm{ABAC}$$$ are not valid solve orders.

Solve order $$$a$$$ is lexicographically smaller than solve order $$$b$$$ if, at the first position where they differ, the character in $$$a$$$ comes in the alphabet before the character in $$$b$$$. E.g., $$$\mathrm{ACB}$$$ is lexicographically smaller than $$$\mathrm{BAC}$$$, which is lexicographically smaller than $$$\mathrm{BCA}$$$.

Consider all possible solve orders of the $$$N$$$ problems. Let their number be $$$M$$$. Sort the $$$M$$$ solve orders from lexicographically smallest to largest. In this list, the median solve order is located at position $$$\lceil \frac{M}{2} \rceil$$$ ($$$\frac{M}{2}$$$ rounded up).

Any team with the median solve order will get a special prize. Help Rubgers students decide what the order is!

Input

The problem consists of $$$T$$$ independent test cases.

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 26$$$) — the number of independent test cases to process.

Each of the next $$$T$$$ lines contains a single integer $$$N$$$ ($$$1 \leq N \leq 26$$$) — the number of problems in the contest.

Output

For each test case, output a single line containing the median solve order for the contest with $$$N$$$ problems.

Example
Input
3
1
2
3
Output
A
AB
BAC
Note

In the first test case, $$$N=1$$$, so the only solve order is $$$\mathrm{A}$$$.

In the second test case, the solve orders in lexicographical order are $$$\mathrm{AB}, \mathrm{BA}$$$. The median is $$$\mathrm{AB}$$$.

In the third test case, the solve orders in lexicographical order are $$$\mathrm{ABC}, \mathrm{ACB}, \mathrm{BAC}, \mathrm{BCA}, \mathrm{CAB}, \mathrm{CBA}$$$. The median is $$$\mathrm{BAC}$$$.