Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Omkar and Last Class of Math

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn Omkar's last class of math, he learned about the least common multiple, or $$$LCM$$$. $$$LCM(a, b)$$$ is the smallest positive integer $$$x$$$ which is divisible by both $$$a$$$ and $$$b$$$.

Omkar, having a laudably curious mind, immediately thought of a problem involving the $$$LCM$$$ operation: given an integer $$$n$$$, find positive integers $$$a$$$ and $$$b$$$ such that $$$a + b = n$$$ and $$$LCM(a, b)$$$ is the minimum value possible.

Can you help Omkar solve his ludicrously challenging math problem?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10$$$). Description of the test cases follows.

Each test case consists of a single integer $$$n$$$ ($$$2 \leq n \leq 10^{9}$$$).

Output

For each test case, output two positive integers $$$a$$$ and $$$b$$$, such that $$$a + b = n$$$ and $$$LCM(a, b)$$$ is the minimum possible.

Example

Input

3 4 6 9

Output

2 2 3 3 3 6

Note

For the first test case, the numbers we can choose are $$$1, 3$$$ or $$$2, 2$$$. $$$LCM(1, 3) = 3$$$ and $$$LCM(2, 2) = 2$$$, so we output $$$2 \ 2$$$.

For the second test case, the numbers we can choose are $$$1, 5$$$, $$$2, 4$$$, or $$$3, 3$$$. $$$LCM(1, 5) = 5$$$, $$$LCM(2, 4) = 4$$$, and $$$LCM(3, 3) = 3$$$, so we output $$$3 \ 3$$$.

For the third test case, $$$LCM(3, 6) = 6$$$. It can be shown that there are no other pairs of numbers which sum to $$$9$$$ that have a lower $$$LCM$$$.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2020 11:58:07 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|