#include<iostream>

struct DP
{
    int firstDigit;
    int length;

    DP(int firstDigit=0, int length=0) : firstDigit(firstDigit), length(length) { }
};

const int MAX_N = 1000, MAX_ANS_LEN = 2*MAX_N;
int N, TpowImodN[MAX_ANS_LEN+10];
DP dp[MAX_N+10][MAX_N+10];

bool reduce(DP& what, DP competitor)
{
    ++competitor.length;
    if (   what.length == 0
        || what.length >  competitor.length
        || what.length == competitor.length && what.firstDigit > competitor.firstDigit)
    {
        what = competitor;
        return true;
    }

    return false;
}

void proceed(int sum, int rem)
{
    for (int lastDigit = 9; lastDigit; --lastDigit)
        reduce(dp[sum+lastDigit][(rem*10+lastDigit)%N], dp[sum][rem]);

    if (reduce(dp[sum][rem*10%N], dp[sum][rem]) && rem*10%N<rem)
        proceed(sum, rem*10%N);
}

void printResult(std::string& res, int sum, int rem, int neededLen)
{
    //std::cout<<"\nPRINT RESULT "<<sum<<" "<<rem<<" "<<neededLen<<"\n";
    if (sum==0 && rem==0 && neededLen==0)
        return;

    int fd =  dp[sum][rem].firstDigit;
    int len = dp[sum][rem].length;
    for (int i = len; i < neededLen; ++i)
        res += '0';
    res += char('0'+fd);
    printResult(res, sum-fd, (N+rem-fd*TpowImodN[len-1]%N)%N, len-1);
}

std::string solve()
{
    TpowImodN[0] = 1%N;
    for (int i = 1; i < MAX_ANS_LEN; ++i)
        TpowImodN[i] = TpowImodN[i-1]*10%N;

    for (int i = 0; i < MAX_N+10; ++i)
        for (int j = 0; j < MAX_N+10; ++j)
            dp[i][j] = 0;
    //starting conditions
    for (int digit = 9; digit >= 0; --digit)
        dp[digit][digit%N] = DP(digit, 1);

    //dp itself
    for (int sum = 1; sum <= N; ++sum)
        for (int rem = 0; rem < N; ++rem)
            if (dp[sum][rem].length)
                proceed(sum, rem);

    //show();

    std::string ans;
    printResult(ans, N, 0, dp[N][0].length);
    return ans;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int t;
    std::cin>>t;
    while (t--)
    {
        std::cin>>N;
        std::cout<<solve()<<"\n";
    }
}