OnesTime Limit: 1000MS Memory Limit: 65536K

Total Submissions: 10306 Accepted: 5869

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

3

7

9901

Sample Output

3

6

12

Source

Waterloo local 2001.06.02

//136K    16MS    C++    273B//题意：求最少个连续的1 mod n为0    //思路：设i个1 %n 余数为 e，i+1个1 为(e*10+1)%n //      当e为0时得到最少个1的数量 #include
     
      int main(void){    int n;    while(scanf("%d",&n)!=EOF)    {        int e=1;        int cnt=1;        while(e!=0){           e=10*e+1;           e%=n;           cnt++;        }        printf("%d\n",cnt);    }    return 0;}