You are given an integer which is a product of LCM and GCD. Your task is to find all the pairs of $$x$$ and $$y$$ for which their product of LCM and GCD is equal to the given number.

Note: Pair $$x$$ and $$y$$ is different from $$y$$ and $$x$$.

Input format

• The first line of the input contains a single integer $$T$$ denoting the number of test cases.
• The first and only line of each test case contains a single Integer.

Output format

For each test case, print a single line containing the Integer.

Constraints

$$1 \le T \le 100$$
$$1 \le N \le 4 \times 10^9$$