题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXVI Olimpiada Informatyczna – I etap Podciągi

请你写一个程序，对于给定的自然数 $n$，生成一个不太长、字符种类不多的字符串，使它正好有 $n$ 个不同的子序列。

具体来说，假设字符串 $w$ 由字符 $w_{1}, w_{2}, \ldots, w_{m}$ 组成。它的子序列是指形如 $w_{i_{1}} w_{i_{2}} \ldots w_{i_{k}}$ 的任意字符串，其中 $0 \leq k \leq m$ 且 $1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq m$。特别地，空字符串（长度为 $0$）也是 $w$ 的子序列。两个子序列若表示的字符串不同，就视为不同。例如，字符串 ioi 有 $7$ 个不同子序列：空字符串以及 i、o、ii、io、oi、ioi。注意，单字符子序列 i 在 ioi 中出现了两次，但只统计一次。

输入格式

输入的第一行是一个自然数 $q$ $(1 \leq q \leq 10000)$，表示输入数据组数。

接下来的 $q$ 行，每行一个自然数 $n$ $(2 \leq n \leq 10^{18})$，表示你生成的字符串需要有的不同子序列数量（包括空子序列）。

输出格式

输出 $q$ 行，每行对应一组输入数据的答案。每行是一个字符串，最多包含 $1000$ 个字符，可以使用数字以及英文大小写字母（这些字符在比较子序列时互不相同）。该字符串需恰好有 $n$ 个不同子序列。

若有多个正确答案，输出任意一个即可。

若无满足条件的答案，输出 !。

5
7
10
42
15
512

ioi
Mmmmm
ERRATA
0000FF
R3GuLaM1N

提示

详细子任务附加限制及分值如下表所示。