Problem Description

To see if a number is divisible by 3, you need to add up the digits of its decimal notation, and check if the sum is divisible by 3. To see if a number is divisible by 11, you need to split its decimal notation into pairs of digits (starting from the right end), add up corresponding numbers and check if the sum is divisible by 11.

For any prime p (except for 2 and 5) there exists an integer r such that a similar divisibility test exists: to check if a number is divisible by p, you need to split its decimal notation into r-tuples of digits (starting from the right end), add up these r-tuples and check whether their sum is divisible by p.

Given a prime int p, find the minimal r for which such divisibility test is valid and output it.

The input consists of a single integer p - a prime between 3 and 999983, inclusive, not equal to 5.

Example

input

3

output

1

input

11

output

2

please, describe how to solve this problem with algorithm.