#include <bits/stdc++.h>
using namespace std;
#define MAX 20005
int value[MAX];
int parent[MAX];
void bfs(int n){
queue<int> q;
q.push(1);
parent[1] = 0;
while(!q.empty()){
int current = q.front();
q.pop();
if(current == 0){
stack<int> st;
while(parent[current]){
st.push(value[current]);
current = parent[current];
}
st.push(1);
while(!st.empty()){
cout<<st.top();
st.pop();
}
cout<<endl;
break;
}
int temp = (current*10)%n;
if(parent[temp]==-1){
q.push(temp);
parent[temp] = current;
value[temp] = 0;
}
temp = (current*10)+1;
temp = temp%n;
if(parent[temp]==-1){
q.push(temp);
parent[temp] = current;
value[temp] = 1;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("input.in","r",stdin);
freopen("output.out","w",stdout);
#endif
int t,n;
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<=n;i++)
parent[i] = -1;
bfs(n);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgTUFYIDIwMDA1CmludCB2YWx1ZVtNQVhdOwppbnQgcGFyZW50W01BWF07Cgp2b2lkIGJmcyhpbnQgbil7CglxdWV1ZTxpbnQ+IHE7CglxLnB1c2goMSk7CglwYXJlbnRbMV0gPSAwOwoJd2hpbGUoIXEuZW1wdHkoKSl7CgkJaW50IGN1cnJlbnQgPSBxLmZyb250KCk7CgkJcS5wb3AoKTsKCQlpZihjdXJyZW50ID09IDApewoJCQlzdGFjazxpbnQ+IHN0OwoJCQl3aGlsZShwYXJlbnRbY3VycmVudF0pewoJCQkJc3QucHVzaCh2YWx1ZVtjdXJyZW50XSk7CgkJCQljdXJyZW50ID0gcGFyZW50W2N1cnJlbnRdOwoJCQl9CgkJCXN0LnB1c2goMSk7CgkJCXdoaWxlKCFzdC5lbXB0eSgpKXsKCQkJCWNvdXQ8PHN0LnRvcCgpOwoJCQkJc3QucG9wKCk7CgkJCX0KCQkJY291dDw8ZW5kbDsKCQkJYnJlYWs7CgkJfQoJCWludCB0ZW1wID0gKGN1cnJlbnQqMTApJW47CgkJaWYocGFyZW50W3RlbXBdPT0tMSl7CgkJCXEucHVzaCh0ZW1wKTsKCQkJcGFyZW50W3RlbXBdID0gY3VycmVudDsKCQkJdmFsdWVbdGVtcF0gPSAwOwoJCX0KCgkJdGVtcCA9IChjdXJyZW50KjEwKSsxOwoJCXRlbXAgPSB0ZW1wJW47CgkJaWYocGFyZW50W3RlbXBdPT0tMSl7CgkJCXEucHVzaCh0ZW1wKTsKCQkJcGFyZW50W3RlbXBdID0gY3VycmVudDsKCQkJdmFsdWVbdGVtcF0gPSAxOwoJCX0KCX0KfQoKaW50IG1haW4oKXsKCgoJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgkjaWZuZGVmIE9OTElORV9KVURHRQoJZnJlb3BlbigiaW5wdXQuaW4iLCJyIixzdGRpbik7CglmcmVvcGVuKCJvdXRwdXQub3V0IiwidyIsc3Rkb3V0KTsKCSNlbmRpZgoKCWludCB0LG47CgljaW4+PnQ7Cgl3aGlsZSh0LS0pewoJCWNpbj4+bjsKCQlmb3IoaW50IGk9MDtpPD1uO2krKykKCQkJcGFyZW50W2ldID0gLTE7CgkJYmZzKG4pOwoJfQoJcmV0dXJuIDA7Cn0=