ONEZERO

#include <iostream>
#include <queue>

#define pi pair<int, string>
#define mp make_pair
using namespace std;

bool visited[20001];
int n;

string bfs()
{
    queue<pi> q;
    q.push(mp(1, "1"));

    pi top;
    long long int r; //remainder
    string m; //number in char


    while(!q.empty())
    {

        top = q.front();
        q.pop();

        r = top.first;
        m = top.second;

        if(r == 0)
        {
            return m;

        }
        if(!visited[r])
        {
            visited[r] = true;

            r *= 10;

            q.push(mp(r % n, top.second + "0"));

            q.push(mp((r + 1) % n, top.second + "1"));


        }

    }
}

int main()
{
    int k;

    cin >> k;
    while(k--)
    {
        cin >> n;

        for(int i = 0; i < 20001; i++)
            visited[i] = false;
        cout << bfs() << endl;
    }
    return 0;
}