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

(a1 + 1) * (a2 + 1) * ... * (ak + 1) = n * a1a2...ak

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

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

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

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

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