Hai ước số

Cho $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Với mỗi $a_i$, hãy tìm hai ước số $d_1>1$ và $d_2>1$ của $a_i$ sao cho $gcd(d_1+d_2,a_i)=1$, hoặc thông báo rằng không tồn tại cặp ước như vậy.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra hai dòng, mỗi dòng gồm $n$ số nguyên:

• Số thứ $i$ của dòng đầu và dòng thứ hai lần lượt là $d_1$ và $d_2$ tương ứng với $a_i$ (thỏa $d_1>1$, $d_2>1$, $d_1\mid a_i$, $d_2\mid a_i$ và $gcd(d_1+d_2,a_i)=1$).
• Nếu không tồn tại cặp ước như vậy, in $-1$ ở cả hai dòng tại vị trí $i$.

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

• $1\le n\le 5·{10}^5$
• $2\le a_i\le {10}^7$

Ví dụ