Processing math: 100%
Digit sum - MarisaOJ: Marisa Online Judge

Digit sum

Time limit: 1000 ms
Memory limit: 256 MB

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≤T≤10000);
  • Each of the following T lines contains a positive integer X (X≥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≤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 106 and S(X) is even for all test cases.
  • Subtask 4 (30 points): The total C(X) across all test cases does not exceed 106.