An and Bình have a positive integer $X$ and want to split it into the sum of two positive integers $A$ and $B$. The true value of a positive integer is not in its magnitude but is determined by the sum of its digits. The two friends will be happy if $A$ and $B$ have equal digit sums.

Objective: There are $T$ test cases, each providing a positive integer $X$. For each test case, help An and Bình find two positive integers $A$ and $B$ such that they add up to $X$ and have equal digit sums.

Input

• The first line contains an integer $T$ ($1 \leq T \leq 10000$);
• Each of the following $T$ lines contains a positive integer $X$ ($X \geq 2$).

Output

• For each test case, print any two positive integers $A$ and $B$ that satisfy the conditions on a single line. If no solution exists, print -1.

Example

Input:

4  
4  
33  
243  
29 

Output:

2 2  
12 21  
117 126
-1

Let $C(X)$ and $S(X)$ denote the number of digits and the digit sum of the positive integer $X$.

Subtasks

• Subtask 1 (20 points): $X \leq 10000$ for all test cases.
• Subtask 2 (30 points): The total $C(X)$ across all test cases does not exceed 1000.
• Subtask 3 (20 points): The total $C(X)$ across all test cases does not exceed $10^6$ and $S(X)$ is even for all test cases.
• Subtask 4 (30 points): The total $C(X)$ across all test cases does not exceed $10^6$.