Rubgers 大学的学生们正在组织一场程序设计竞赛。由于将有很多强队参赛，他们预计其中一些队伍会解决所有题目。为了区分他们，将向拥有特殊解题顺序的队伍颁发一个特别奖。

比赛包含 $N \le 26$ 道题目，标记为 A, B 等：即英文字母表的前 $N$ 个字母。

队伍的解题顺序是一个字母序列，表示其解决所有题目的顺序：例如，对于 $N = 3$，一个可能的解题顺序是 BAC —— 先解决 B，然后是 A，最后是 C。我们只考虑恰好解决每道题一次的队伍，因此，例如 AC 或 ABAC 都不是有效的解题顺序。

如果在第一个不同的位置上，解题顺序 $a$ 中的字符在字母表中排在解题顺序 $b$ 中的字符之前，则称解题顺序 $a$ 的字典序小于解题顺序 $b$。例如，ACB 的字典序小于 BAC，而 BAC 的字典序又小于 BCA。

考虑这 $N$ 道题的所有可能解题顺序。设其数量为 $M$。将这 $M$ 个解题顺序按字典序从小到大排序。在这个列表中，中位数解题顺序位于第 $\lceil \frac{M}{2} \rceil$ 个位置（即 $M/2$ 向上取整）。

任何获得中位数解题顺序的队伍都将获得特别奖。帮助 Rubgers 的学生们确定这个顺序是什么！

输入格式

本题包含 $T$ 个独立的测试用例。

第一行包含一个整数 $T$ ($1 \le T \le 26$) —— 需要处理的独立测试用例数量。

接下来的 $T$ 行中，每行包含一个整数 $N$ ($1 \le N \le 26$) —— 比赛中的题目数量。

输出格式

对于每个测试用例，输出一行，包含具有 $N$ 道题目的比赛的中位数解题顺序。

样例

输入样例 1

3
1
2
3

输出样例 1

A
AB
BAC

说明

在第一个测试用例中，$N = 1$，因此唯一的解题顺序是 A。

在第二个测试用例中，按字典序排列的解题顺序为 AB, BA。中位数是 AB。

在第三个测试用例中，按字典序排列的解题顺序为 ABC, ACB, BAC, BCA, CAB, CBA。中位数是 BAC。