Олимпиадный тренинг

Задача 38575. Псевдопростые числа


Пусть a1 = 2, a2 = 3, an = aa2·...·an-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<

Входные данные
Вводится одно натуральное число X, 1 < X ≤ 109.

Выходные данные
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
 
Примеры
Входные данные Выходные данные
1 6 2 3
2 5 5
3 7 0