CRZr5z - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;

long long t, n, a[10000000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    a[1] = 9;
    for (int i = 2; i <= 4500; i++)
    {
        if (i%2 == 0) a[i] = 10 * a[i/2];
        else a[i] = 10 * a[i/2] + 9;
    }

    cin >> t;
    for (int i = 1;i <= t; i++)
    {
        cin >> n;
        for (int i = 1; i <= 4500; i++)
            if (a[i] % n == 0)
            {
                cout << a[i] << '\n';
                break;
            }
    }
    return 0;
}