Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sum of GCD and LCM

By Sajjat004 · 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

Discussion

Statistics


44% Solution Ratio

Azizur_RahmanEarliest, 4M ago

MR.Jukerburg11Fastest, 0.0s

mdarafat1819Lightest, 1.2 MB

YouKnowWhoShortest, 674B

Submit

Login to submit