URI Online Judge | 1213

Ones

By Piotr Rudnicki Russia

Timelimit: 1

Given any integer n (1 ≤ n ≤ 10000) not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1\'s. How many digits are in the smallest such a multiple of n?

Input

The input consists in many test cases and ends with EOF. Each test case contains one integer n (1 ≤ n ≤ 10000) not divisible by 2 or 5.

Output

For each test case, print how many digits have the multiple of n that attends the above requisites.

Sample Input Sample Output

3
7
9901

3
6
12