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

Output

Sample Input

Sample Output

HINT

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int main(){    int n,count1=0;    long long m;    while(~scanf("%d",&n))    {        m=1;        count1=1;        while(m%=n)        {            m=m*10+1;            count1++;        }    printf("%d/n",count1);    }    return 0;}