Zenyk and GCD

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk loves numbers. And even more, Zenyk loves a lot of numbers.

It would seem that very little is needed for happiness. To write down many numbers for himself and attain Zen. But no. Marichka comes and ruins everything. You see, all the numbers must be written in a row, the sum of all numbers must be equal to \(s\), and the GCD of every two adjacent numbers must be different from one.

The GCD of two numbers is the greatest common divisor, the largest such integer that both numbers are divisible by without a remainder.

Help Zenyk determine the maximum number of integers he can write if he still follows Marichka’s conditions.

Input

The single line contains a single integer \(s\) — the number Marichka mentioned in her conditions.

Output

In the single line, print a single integer — the maximum number of integers Zenyk can write while following Marichka’s conditions.

Constraints

\(2 \le s \le 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4	2

Notes

Zenyk can write two numbers: 2, 2.