Твори

Нехай 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.

Приклади