13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T724,

You are given $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$.

For each $$$a_i$$$ find its two divisors $$$d_1 \gt 1$$$ and $$$d_2 \gt 1$$$ such that $$$\gcd(d_1 + d_2, a_i) = 1$$$ (where $$$\gcd(a, b)$$$ is the greatest common divisor of $$$a$$$ and $$$b$$$) or say that there is no such pair.

Input

The first line contains single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 10^7$$$) — the array $$$a$$$.

Output

To speed up the output, print two lines with $$$n$$$ integers in each line.

The $$$i$$$-th integers in the first and second lines should be corresponding divisors $$$d_1 \gt 1$$$ and $$$d_2 \gt 1$$$ such that $$$\gcd(d_1 + d_2, a_i) = 1$$$ or $$$-1$$$ and $$$-1$$$ if there is no such pair. If there are multiple ans

Two Divisors

Examples