Обернений факторіал

Limits: 1 sec., 256 MiB

Олеся працює в компанії, яка займається серйозними математичними обчисленнями.

В один день керівницство поставило перед нею задачу створення програми, яка по заданому факторіалу \(n!\) натурального числа \(n\) має повертати це саме число. Олеся не має ідей, як це можна було б зробити, і просить вас допомогти їй.

Факторіал \(n!\) натурального числа \(n\) - це добуток всіх натуральних чисел*, менших або рівних \(n\). Наприклад:

\(21! = 1 \times 2 \times 3 \times \ldots \times 21 = 51\space090\space942\space171\space709\space440\space000\)

Задача знаходження факторіала малого числа є досить простою і, скоріше за все, вам вже доводилося її розв’язувати багато разів. В цей же раз ваше завдання обернене - вам дано значення \(n!\) і вам потрібно знайти значення \(n\).

* Вважаємо, що натуральні числа - це додатні цілі числа.

Блоки тестів

• Блок 1: 5 балів, \(n! \leq 1.4 \cdot 10^{12}\).

• Блок 2: 25 балів, \(len(n!) \leq 100\).

• Блок 3: 70 балів, без додаткових обмежень.

Input

У першому рядку задано одне ціле число \(n!\) — факторіал \(n!\) деякого натурального числа \(n\).

Output

В єдиному рядку виведіть одне ціле додатне число \(n\) — шуканий обернений факторіал.

Constraints

Позначимо через \(len(n!)\) довжину \(n!\):

\(1 \leq len(n!) \leq 10^6\)

Samples

Input (stdin) сopy	Output (stdout) сopy
120	5

Input (stdin) сopy	Output (stdout) сopy
51090942171709440000	21

Input (stdin) сopy	Output (stdout) сopy
10888869450418352160768000000	27