Ones

1000ms    65536K
200    99
Beginner

Description

Given any integer 0 < 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

Each line contains a number n.

Output

Output the number of digits.

Sample Input

1
3 
7 
9901

Sample Output

1
3
6
12

Source

Editor

keefo on 2013-11-12 02:48:07


North University of China

OnlineJudge

NUC

NOJ

OJ

ACM/ICPC