#$4921$. 「POI2019 R1」子序列 Subsequences

题目描述

题目译自 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$

数据范围与提示

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