Hide

Problem K
Meow Factor

/problems/meowfactor/file/statement/en/img-0001.jpg
Picture via pxhere, cc0
Among many of the Catland club kittens it is important to keep a paw on the pulse of the latest fashions and trends in order to stay hip. When a new number is discovered in Catland, its coolness is primarily determined by its meow factor. For a positive integer $n$, its meow factor is the largest integer $m$ such that $n$ is evenly divisible by $m$ nine times (once for each life of a cat). We say that $n$ is divisible by $m$ nine times if, starting with $n$, you can divide it by $m$ without a remainder, take the result of the division and again divide it by $m$ without a remainder, and so on, dividing by $m$ nine times in total.

While some cats are naturally chic and have an innate ability to see the meow factor of numbers, others who struggle to stay in vogue can not even tell the difference between $3\, 584$ and $4\, 711$ (the former clearly having a higher meow factor). Can you help those poor unfortunate cats lacking a sense of style, by writing a program to determine the meow factor of a number?

Input

The input contains a single integer $n$ ($1 \le n \le 2^{63}-1$).

Output

Output the meow factor of $n$.

Sample Input 1 Sample Output 1
3584
2
Sample Input 2 Sample Output 2
4711
1

Please log in to submit a solution to this problem

Log in