编写一个程序，对于给定的非负整数 $n$，生成一个在小规模字母表上的相对较短的字符串，使其恰好拥有 $n$ 个不同的子序列。

形式化地，设 $w$ 是由连续字符 $w_1, w_2, \dots, w_m$ 组成的字符串。那么任何形式为 $w_{i_1}w_{i_2}\dots w_{i_k}$ 的字符串，其中 $0 \le k \le m$ 且 $1 \le i_1 < i_2 < \dots < i_k \le m$，都被称为 $w$ 的一个子序列。特别地，空字符串（0 个字母）也是 $w$ 的一个子序列。如果两个子序列所代表的字符串不同，则称它们是不同的。例如，字符串 ioi 有七个不同的子序列：空子序列、i、o、ii、io、oi 和 ioi。注意，单字母子序列 i 在 ioi 中出现了两次，但它只被计算一次。

输入格式

标准输入的第一行包含一个正整数 $q$ ($1 \le q \le 10\,000$)，表示测试数据的组数。接下来的 $q$ 行描述这些测试数据。每行包含一个正整数 $n$ ($2 \le n \le 10^{18}$)，即所生成的字符串需要拥有的子序列数量（包含空子序列）。

输出格式

你的程序应向标准输出打印恰好 $q$ 行，对应各组输入数据的答案。每行应包含一个长度不超过 1000 的字符串，其中的每个字符可以是任意数字或任意英文字母（大小写均可）；在比较子序列时，所有这些字符都是可区分的。输出的字符串必须恰好拥有 $n$ 个不同的子序列。

如果存在多个正确的答案，接受其中任何一个即可。

如果不存在满足要求的字符串，则打印字符 !（感叹号）代替字符串。

样例

输入 1

5
7
10
42
15
512

输出 1

ioi
Mmmmm
ERRATA
0000FF
R3GuLaM1N

子任务

测试集由以下子任务组成。每个子任务内可能包含多个单元测试。