Your task is to find a range $L$ to $R$ (inclusive) such that the number of integers in this range that satisfies the following property is equal to $K$:

• Property: Sum of all the subsequences of digits of that number must be odd

For example, 1257 has 1 + 2 + 5 + 7 + 12 + 15 + 17 + 25 + 27 + 57 + 125 + 127 + 257 + 1257 = 1934 as the sum of all subsequences.

Find such a range that is of the minimum length. If more than one such range exists, print the range with the smallest value of $L$.

Input format

• The first line contains an integer $Q$ denoting the number of queries.
• The next $Q$ lines contain an integer $K$.

Output format

For each query, print two integers denoting $L$ $R$ in a separate line. If no such range exists, then print -1.

Constraints
$1 \le Q \le 1e5\\ 1 \le K \le 1e5$