#include<bits/stdc++.h>
#define pb push_back
#define ull unsigned long long int
#define maxx 100
#define sqF sqrt(5.0)
#define phi (1+sqF)/2
using namespace std;
int X[]={+1,-1,-1,+1,+2,-2,+2,-2};
int Y[]={+2,+2,-2,-2,+1,+1,-1,-1};
map<string,bool>vis;
bool check(string s,int n)
{
    int ans=0;
    for(int i=0;i<s.length();i++)/**< This function is to check if our number in form of string is divisible by n or not */     
     ans=(ans*10+s[i]-'0')%n;
    ans=ans%n;
    if(ans==0){ return true;}
    return false;
}
string bfs(string s,int n)
{
    vis[s]=true;
    queue<string>Q;
    Q.push(s);
    if(check(s,n))return s;
    while(not Q.empty())
    {
        string src=Q.front();
        if(check(src,n)==true)return src;
        Q.pop();
        string t=src+"1";
        vis[t]=true;
        string t2=src+"0";
        vis[t2]=true;
        Q.push(t2);
        Q.push(t);
    }
}
int main() {
        ios_base::sync_with_stdio(false);
        int t;
    	cin>>t;
    	while(t--)
        {
            int n;
            cin>>n;
            if(n==0)
                cout<<"0"<<endl;
            else
            {
              string ans=bfs("1",n);
              cout<<ans<<endl;
            }
            vis.clear();
        }
    return 0;
}