Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Let's call a positive integer $M$ a beautiful number if the following conditions are satisfied:
The decimal representation of $M$ (without leading zeros) does not contain any zeros.
The sum of squares of all decimal digits of $M$ is a perfect square.

For example, $1$, $4$ and $221$ are beautiful, but $10$ and $333$ are not.

You are given a positive integer $N$. Find the smallest $N$-digit beautiful number or determine that all $N$-digit integers are not beautiful.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single integer $N$.

------ Output ------
For each test case, print a single line containing one integer ― the smallest $N$-digit beautiful number, or $-1$ if there is no such number.

------ Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{6}$
the sum of $N$ over all test cases does not exceed $10^{6}$

------ Subtasks ------
Subtask #1 (10 points): $1 ≤ N ≤ 100$

Subtask #2 (90 points): $1 ≤ T ≤ 10$

----- Sample Input 1 ------
2

1

2
----- Sample Output 1 ------
1

34
----- explanation 1 ------
Example case 1: It is obvious that $1$ is the smallest beautiful number.

Example case 2: $34$ is beautiful because $3^{2} + 4^{2} = 9 + 16 = 25 = 5^{2}$. On the other hand, we can prove that this is the smallest beautiful number.

见题面

见题面