問題文

正整数 $N$ が与えられます。

数字（0123456789 のいずれか）のみからなる文字列 $X$ に対して $\mathcal{P}(X)$ を、$X$ の空でない（連続とは限らない）部分列を整数と解釈した値としてあり得るもの全体の集合と定義します。
例えば、 $x$ を 102 としたとき $\mathcal{P}(x) = \{0, 1, 2, 10, 12, 102 \}$ です。

また、 $\mathrm{mex}~\mathcal{P}(X)$ を $\mathcal{P}(X)$ に含まれない最小の非負整数と定義します。

数字のみからなる長さ $N$ の文字列 $S$ のうち、 $\mathrm{mex}~\mathcal{P}(S)$ としてあり得る最大値を $M$ とします。
$\mathrm{mex}~\mathcal{P}(S') = M$ を満たす数字のみからなる長さ $N$ の文字列 $S'$ を $1$ つ提示してください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1 \leq T \leq 1000$
• $1 \leq N \leq 5 \times 10^5$
• すべてのテストケースにわたる $N$ の総和は $5 \times 10^5$ を超えない
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられる。

$N$

出力

各テストケースについての答えを順に改行区切りで出力せよ。

ただし、条件を満たす $S'$ が複数ある場合、そのいずれを答えても正解と判定される。

サンプル

3
3
1
12

102
0
214567893012