#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;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSB1bGwgdW5zaWduZWQgbG9uZyBsb25nIGludAojZGVmaW5lIG1heHggMTAwCiNkZWZpbmUgc3FGIHNxcnQoNS4wKQojZGVmaW5lIHBoaSAoMStzcUYpLzIKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IFhbXT17KzEsLTEsLTEsKzEsKzIsLTIsKzIsLTJ9OwppbnQgWVtdPXsrMiwrMiwtMiwtMiwrMSwrMSwtMSwtMX07Cm1hcDxzdHJpbmcsYm9vbD52aXM7CmJvb2wgY2hlY2soc3RyaW5nIHMsaW50IG4pCnsKICAgIGludCBhbnM9MDsKICAgIGZvcihpbnQgaT0wO2k8cy5sZW5ndGgoKTtpKyspLyoqPCBUaGlzIGZ1bmN0aW9uIGlzIHRvIGNoZWNrIGlmIG91ciBudW1iZXIgaW4gZm9ybSBvZiBzdHJpbmcgaXMgZGl2aXNpYmxlIGJ5IG4gb3Igbm90ICovICAgICAKICAgICBhbnM9KGFucyoxMCtzW2ldLScwJyklbjsKICAgIGFucz1hbnMlbjsKICAgIGlmKGFucz09MCl7IHJldHVybiB0cnVlO30KICAgIHJldHVybiBmYWxzZTsKfQpzdHJpbmcgYmZzKHN0cmluZyBzLGludCBuKQp7CiAgICB2aXNbc109dHJ1ZTsKICAgIHF1ZXVlPHN0cmluZz5ROwogICAgUS5wdXNoKHMpOwogICAgaWYoY2hlY2socyxuKSlyZXR1cm4gczsKICAgIHdoaWxlKG5vdCBRLmVtcHR5KCkpCiAgICB7CiAgICAgICAgc3RyaW5nIHNyYz1RLmZyb250KCk7CiAgICAgICAgaWYoY2hlY2soc3JjLG4pPT10cnVlKXJldHVybiBzcmM7CiAgICAgICAgUS5wb3AoKTsKICAgICAgICBzdHJpbmcgdD1zcmMrIjEiOwogICAgICAgIHZpc1t0XT10cnVlOwogICAgICAgIHN0cmluZyB0Mj1zcmMrIjAiOwogICAgICAgIHZpc1t0Ml09dHJ1ZTsKICAgICAgICBRLnB1c2godDIpOwogICAgICAgIFEucHVzaCh0KTsKICAgIH0KfQppbnQgbWFpbigpIHsKICAgICAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgICAgICBpbnQgdDsKICAgIAljaW4+PnQ7CiAgICAJd2hpbGUodC0tKQogICAgICAgIHsKICAgICAgICAgICAgaW50IG47CiAgICAgICAgICAgIGNpbj4+bjsKICAgICAgICAgICAgaWYobj09MCkKICAgICAgICAgICAgICAgIGNvdXQ8PCIwIjw8ZW5kbDsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgc3RyaW5nIGFucz1iZnMoIjEiLG4pOwogICAgICAgICAgICAgIGNvdXQ8PGFuczw8ZW5kbDsKICAgICAgICAgICAgfQogICAgICAgICAgICB2aXMuY2xlYXIoKTsKICAgICAgICB9CiAgICByZXR1cm4gMDsKfQo=