Добутки#8581

Добутки

1 секунда

128 мегабайтів

Середня

Нехай $n$ — натуральне число. Георгій хоче знайти такі натуральні числа $a_{1}$ a_1, $a_{2}$ a_2, ..., $a_{k}$ a_k, що їхній добуток збільшиться в $n$ разів, якщо до кожного з них додати $1$ .

(a_{1} + 1) \cdot (a_{2} + 1) \cdot \dots \cdot (a_{k} + 1) = n \cdot a_{1} a_{2} \dots a_{k}

(a_1 + 1) \cdot (a_2 + 1) \cdot \ldots \cdot (a_k + 1) = n \cdot a_1 a_2 \ldots a_k

Тепер він хоче дізнатися, для якого найменшого значення $k$ це можливо. Напишіть програму, яка розв'язує задачу Георгія.

Вхідні дані

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

Вихідні дані

Виведіть потрібне значення $k$ .

Приклади

Приклад 1

Loading

a_{1}

a_{2}

a_{k}

(a_{1} + 1) \cdot (a_{2} + 1) \cdot \dots \cdot (a_{k} + 1) = n \cdot a_{1} a_{2} \dots a_{k}

2 < n < 1000