F. Erdős-Straus Conjecture
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given that IOI 2023 was in Hungary and IOI 2024 will be in Egypt, what better than a problem about a conjecture of Hungarian mathematicians about Egyptian fractions!

The Erdős-Straus conjecture states that for every integer $$$n \geq 2$$$, there exist positive integers $$$x$$$, $$$y$$$, $$$z$$$ such that

$$$$$$\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}.$$$$$$

Since this problem is very difficult, you are asked to solve a variant in which $$$z=xy$$$. That is, given $$$n \geq 1$$$, you must find a pair of positive integers $$$x$$$, $$$y$$$ such that

$$$$$$\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{xy}$$$$$$

if they exist.

Input

The input begins with an integer $$$T$$$, the number of test cases. Then follow $$$T$$$ lines, each with an integer $$$n$$$.

Output

For each test case, you should print a line with the two positive integers $$$x$$$, $$$y$$$ separated by spaces, or with a single $$$0$$$ in case those numbers do not exist. If there are multiple valid pairs of integers $$$x$$$, $$$y$$$, you can print any of them.

Scoring
  1. (8 points) $$$n \leq 10$$$.
  2. (7 points) $$$n \leq 100$$$.
  3. (10 points) The sum of $$$n$$$ for all cases is at most $$$5 \cdot 10^6$$$.
  4. (20 points) $$$n$$$ is even.
  5. (55 points) No additional constraints.
Example
Input
4
2
1
5
6
Output
2 1
0
2 5
3 4
Note

$$$1 \leq T \leq 100$$$. $$$1 \leq n \leq 10^9$$$.