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$