Limits 1s, 512 MB

The greatest common divisor (GCD) of two integers, is the largest integer that divides both of the integers. For example : GCD (2, 4) = 2.
The least common multiple (LCM) of two integers, is the smallest positive integer that is divisible by both of the integers. For example :LCM (2, 4) = 4.

Recently, Paltu learn about GCD and LCM. For checking his knowledge about GCD and LCM, his friend give him a challenge to solve the following problem.

In this problem, you will be given a positive integer N. You have to find two positive
integers A and B (1A, B < N) so that GCD ( A , B) + LCM (A , B) = N and A + B = N.
If there are multiple answer, you have to find those A and B whose difference (abs(A – B)) is the smallest.

Input

The first line contains an integer T (1 ≤ T ≤ 105) — denoting the numbers of test case.
Each of the next T lines contains an integer N (1 ≤ N ≤ 108)

Output

For each test case, if it is possible to find A and B, print them in a line separated
by a space (print the smallest first), otherwise print -1.

Sample

InputOutput
2
6
10
3 3
5 5

Submit

Login to submit.

Statistics

46% Solution Ratio
Azizur_RahmanEarliest, May '20
JIANEEFastest, 0.0s
JIANEELightest, 5.5 kB
rkb_rdShortest, 489B
Toph uses cookies. By continuing you agree to our Cookie Policy.