#include <bits/stdc++.h>

using namespace std;

//******************************************************************
// HackerRank Prepare > Mathematics > Fundamentals: Special Multiple
//******************************************************************

static constexpr int N = 32;

#if 0
    uint64_t result = 0;
    uint64_t i = 1, mod;
    while( n > 0)
    {
        if((n % 2) == 1) 
            mod=9;
        else
            mod=0;
        result += mod * i;
        i = i*10;
        //cout << "n: " << n
        //     << " mod: " << mod
        //     << " i: " << setw(5) << i
        //     << " result: " << setw(5) << result << endl;
        n = n/2;
    }
#endif    

string solve(int n) 
{
    auto genNinesAndZeros = [](int n)
    {
        // 0001 ==>   9
        // 0010 ==>  90
        // 0011 ==>  99
        // 0100 ==> 900
        // 0101 ==> 909
        // ...
        
        bitset<N> bs{(uint64_t)n};
        //cout << bs << endl;
        uint64_t val = 0;
        uint64_t mult = 1;
        for (int i = 0; i < N; i++)
        {
            if (bs.test(i) == true)
                val += 9 * mult;
            else
                val += 0 * mult;
            mult *= 10;
        }
        return val;
    };
    
    vector<uint64_t> ninesAndZerosVec;
    for (int i = 1; i < 5000; i++)
        ninesAndZerosVec.push_back(genNinesAndZeros(i));    

    for (auto i: ninesAndZerosVec)
        if (i % n == 0)
            return to_string(i);
    return "not found";
}

    
int main()
{
    vector<pair<int,int>> testCases = {{5,90},{7,9009},{1,9}};

    for (auto i: testCases)
    {
        string res = solve(i.first);
        cout << res << endl;
        cout << i.second << endl;
        cout << "-----------\n";
    }
    
    return 0;
}