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 + 157 + 257 + 1257 = 2091 as the sum of all subsequences.

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

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\leq Q \leq 10^5$

$1\leq K \leq 10^5$