Problem Statement

You are given a positive integer $N$.

For a string $X$ consisting only of digits (any of 0123456789), define $\mathcal{P}(X)$ as the set of all possible values obtained by interpreting a non-empty (not necessarily contiguous) subsequence of $X$ as an integer.
For example, when $x$ is 102, we have $\mathcal{P}(x) = \{0, 1, 2, 10, 12, 102 \}$.

Also, define $\mathrm{mex}~\mathcal{P}(X)$ as the smallest non-negative integer not contained in $\mathcal{P}(X)$.

Let $M$ be the maximum possible value of $\mathrm{mex}~\mathcal{P}(S)$ over all strings $S$ of length $N$ consisting only of digits.
Present $1$ string $S'$ of length $N$ consisting only of digits that satisfies $\mathrm{mex}~\mathcal{P}(S') = M$.

You are given $T$ test cases; answer each of them.

Constraints

• $1 \leq T \leq 1000$
• $1 \leq N \leq 5 \times 10^5$
• The sum of $N$ over all test cases does not exceed $5 \times 10^5$
• All inputs are integers

Input

The input is given from standard input in the following format.

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

Each test case is given in the following format.

$N$

Output

Output the answers for the test cases in order, separated by newlines.

If there are multiple strings $S'$ satisfying the condition, any of them will be accepted.

Sample

3
3
1
12

102
0
214567893012