P12775 [POI 2018/2019 R1] 子序列 Subsequences

翻译来自于 [LibreOJ](https://loj.ac/p/4921)。

**题目译自 [XXVI Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi26-1/dashboard/) [Podciągi](https://sio2.mimuw.edu.pl/c/oi26-1/p/pod/)** 请你写一个程序，对于给定的自然数 $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$ 个不同子序列。 若有多个正确答案，输出任意一个即可。 若无满足条件的答案，输出 `!`。

详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | 每个 $n$ 的质因数分解之和不超过 $300$ | $20$ | | $2$ | 每个 $n$ 是两个 $2$ 的幂之差 | $10$ | | $3$ | $n$ 的二进制不以 `01` 或 `010` 结尾，且无相邻 `0` | $10$ | | $4$ | $n \leq 10^{6}$，随机生成 | $20$ | | $5$ | $n \leq 10^{18}$，随机生成 | $30$ | | $6$ | $n \leq 10^{18}$，非随机生成 | $10$ |