Solution of 10127 - Ones

Problem description:
source: https://uva.onlinejudge.org/external/101/10127.html

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

A fle of integers at one integer per line.

Output


Each output line gives the smallest integer x > 0 such that p = ∑x i=0 -1 1 × 10i = a × b, where a is the corresponding input integer, and b is an integer greater than zero.

Sample Input

37
9901

Sample Output

36
12

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <fstream>
#include <iostream>
#include<stdio.h>
#include<stdlib.h>

using namespace std;

int main()
{
    int input,k,one,dividend;
    while(scanf("%d",&input)==1)
    {
        dividend=1;
        one=1;
        if(input==0)
            printf("0\n");
        else
        {
            do{
                if(dividend<input)
                {
                    dividend=(dividend*10)+1;
                    one+=1;
                }
                k=dividend%input;
                if(k!=0)
                    dividend=k;
            }while(k!=0);
            printf("%d\n",one);
        }

    }
    return 0;
}