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
