Вам заданы \(n\) целых чисел \(a_1, a_2, \dots, a_n\).
Для каждого \(a_i\) найдите два его делителя \(d_1 > 1\) и \(d_2 > 1\) такие, что \(\gcd(d_1 + d_2, a_i) = 1\) (где \(\gcd(a, b)\) — наибольший общий делитель \(a\) и \(b\)) или скажите, что такой пары нет.
Выходные данные
Ради ускорения вывода, выведите ответы в две строки по \(n\) чисел в каждой.
В первой и второй строках \(i\)-ми по счету числами выведите соответствующие делители \(d_1 > 1\) и \(d_2 > 1\) такие, что \(\gcd(d_1 + d_2, a_i) = 1\) или \(-1\) и \(-1\), если такой пары делителей нет. Если существует несколько подходящих ответов, выведите любой из них.
Примечание
Рассмотрим \(a_7 = 8\). У него есть \(3\) делителя больших, чем \(1\): \(2\), \(4\), \(8\). Не сложно заметить, что сумма любой пары делителей делится на \(2\), также как и \(a_7\).
Существуют и другие подходящие пары делителей \(d_1\) и \(d_2\) для \(a_{10}=24\), например, \((3, 4)\) или \((8, 3)\). Вы можете вывести любую из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
2 3 4 5 6 7 8 9 10 24
|
-1 -1 -1 -1 3 -1 -1 -1 2 2
-1 -1 -1 -1 2 -1 -1 -1 5 3
|