Inverse factorial

Given a huge number that is some factorial n!, recover the integer n. The input can have up to a million digits.

Medium6MathNumber theoryBinary searchImplementationNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

Given a positive integer $n$ , computing the factorial $n!$ is easy. This time the direction is reversed: you are given $n!$ and have to recover $n$ .

Input

The first line contains $n!$ for some natural number $n$ . The number of digits of $n!$ is at most $10^6$ . The input is always the factorial of some natural number, and $n$ is at least 1.

Output

Print $n$ on the first line.