Пусть a
1 = 2, a
2 = 3, a
n = a
1·a
2·...·a
n-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<
Входные данные
Вводится одно натуральное число X, 1 < X ≤ 10
9.
Выходные данные
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 |
2 3 |
| 2 |
5 |
5 |
| 3 |
7 |
0 |