Произведения

Пусть n - натуральное число. Георгий хочет найти натуральные числа a[1], a[2], ..., a[k], произведение которых увеличится в n раз если к каждому из них прибавить 1.

(a[1] + 1) * (a[2] + 1) * ... * (a[k] + 1) = n * a[1]a[2]...a[k]

Теперь он хочет узнать, для какого наименьшего значения k это возможно. Напишите программу, которая решает задачу Георгия.

Входные данные

Целое число n (2 < n < 1000).

Выходные данные

Вывести требуемое значение k.

Примеры