UVa ones

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
typedef unsigned int uint;
typedef long long int llint;
typedef pair<int, int> pii;

llint solve(llint a);
llint bigMod(llint b, llint p, llint m);

//========================\\main//========================//
int main()
{
    llint a;

    while(cin >> a)
    {
        cout << solve(a) << '\n';
    } // end of while

    return 0;
}
//========================\\main//========================//

llint solve(llint a)
{
    llint sumMod = 0;
    llint res = 1;
    int temp;

    for(llint i = 0; ; i++)
    {
        sumMod += bigMod(10, i, a);

        // cout << (int)myPow(10, i) << '\n';
        if( (sumMod % a) == 0 ) return i + 1;

        // cout << res << endl;
        //res = res * 10;
    } // end of for
}///////////////////////////////////////////////////////////

llint bigMod(llint b, llint p, llint m)
{
    if(p == 0)
    {
        return 1 % m;
    }

    if(p%2 == 0)
    {
        llint ret = bigMod(b, p / 2, m);
        return ( (ret % m) * (ret % m) ) % m;
    }
    else
    {
        return ((b % m) * (bigMod(b, p - 1, m) % m)) % m;
    }
} /////////////////////////////////////