And again the chain#4515

And again the chain

1 second
64 megabytes
Easy

Consider a chain consisting of rings. Determine the minimum number of rings that must be unlinked so that the remaining segments can be rearranged to form chains of any length from to rings. The unlinked rings can be reused when forming new chains.

For example, if N = 21, it is enough to unlink just rings to create segments of lengths , , and . The two unlinked rings are considered as chains of length one.

Write a program that, given a natural number (the length of the initial chain), calculates the minimum number of rings that must be unlinked to achieve the described goal.

Input

The input consists of a single integer (1 \le N \le 10^9).

Output

Output a single integer representing the minimum number of rings that must be unlinked.

Examples

Example 1

Loading
Loading