Question
N Triplets
Alisha is still not satisfied with Harsh's math skills so she gave him a new challenge.
Given a positive integer N, find any 3 distinct positive integers A, B, C such that:
- The product of any two of these 3 integers is a divisor of N.
- The product of all three integers is a multiple of N.
If multiple solutions exist, you may print any of them. Print -1 if no solution exists.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
The first and only line of each test case contains a single integer, N.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 109
The first and only line of each test case contains a single integer, N.
Constraints
1 ≤ T ≤ 100
1 ≤ N ≤ 109
Output
For each test case, output on a new line three space-separated integers satisfying the given condition.
Print -1 if the answer does not exist.
Print -1 if the answer does not exist.
Example
Input
2
30
24
Output
2 3 5
2 6 4
Explanation
Test case 1: We have A = 2, B = 3, C = 5. They satisfy all the conditions:
AB = 6, AC = 10, BC = 15 are all divisors of N = 30.
ABC = 30 is a multiple of N = 30
Test case 2: We have A = 2, B = 6, C = 4. They satisfy all the conditions:
AB = 12, AC = 8, BC = 24 are all divisors of N = 24.
ABC = 48 is a multiple of N = 24
2
30
24
Output
2 3 5
2 6 4
Explanation
Test case 1: We have A = 2, B = 3, C = 5. They satisfy all the conditions:
AB = 6, AC = 10, BC = 15 are all divisors of N = 30.
ABC = 30 is a multiple of N = 30
Test case 2: We have A = 2, B = 6, C = 4. They satisfy all the conditions:
AB = 12, AC = 8, BC = 24 are all divisors of N = 24.
ABC = 48 is a multiple of N = 24