You are given an integer $$K$$.

Find the smallest number $$N$$ such that $$N$$ has exactly $$K$$ digits and none of the digits in $$N$$ is $$0$$. Also, the product of digits in number $$N$$ is greater than or equal to the sum of digits in number $$N$$.

Input format

• The first line contains an integer $$T$$ denoting the number of test cases.
• For each test case, the first line contains an integer $$K$$.

Output format

For each test case in a new line, print the smallest number $$N$$ that satisfies the given condition.

Constraints

\(1 \le T \le 10 \\ 1 \le K \le 5 \times 10^5\)