Find Repunit(Self-made)

Problem
Repunit is a natural number that contains only the digit 1 (for example, 1,11,111,1111,and so on.).

If natural number n and 10 are coprime, some repunit exists that is n's multiple.
For example, 111 is 3's multiple and repunit.111111 is 7's multiple and repunit.

Get the smallest repunit which is n's multiple. n is smaller than 10^8.

Input
Single natural number n. n and 10 are coprime.

Output

The smallest repunit's digit number.

Example

Input -> Output

3    -> 3 (=111)

7    -> 6 (=111111)

11  -> 2

99  -> 18

27  -> 27

Explanation

R(k) means k-th repunit. R(1)=1,R(2)=11, and so on.

The following recurring formula consists. 

R(k+1)=10R(k)+1

So, sulplus of n is next.

R(k+1)%n=(10%n*R(k)%n+1%n)%n

Use this, We can calculate the answer.

Sample Answer Code(C)

#include<stdio.h>

int main(void){

  unsigned int m,n,i,k,s;

  scanf("%u",&m);

  for(n=0;;n++){

    for(i=0;i<=n;i++){

      if(i==0){

s=1%m;

k=1;

      }else{

k*=10;

k%=m;

s+=k;

s%=m;

      }

    }

    if(s==0){

      printf("%d\n",n+1);

      break;

    }

  }

  return 0;

}