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

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

Формат выходных данных
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.