1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<queue>
 6 using namespace std;
 7 
 8 const int maxn=1000;
 9 
10 int p[maxn],pre[maxn];
11 
12 void print(int m){
13     if(m==-1) return;
14     print(pre[m]);
15     printf("%d",p[m]);
16 }
17 
18 void BFS(int n){
19     queue<int> q;
20     q.push(1);
21     p[1]=1,pre[1]=-1;
22     while(q.size()){
23         int v=q.front();
24         q.pop();
25         int x=(v*10)%n;
26         int y=(v*10+1)%n;
27         if(x==0){
28             print(v);
29             cout<<"0"<<endl;
30             break;
31         }
32         if(y==0){
33             print(v);
34             cout<<"1"<<endl;
35             break;
36         }
37         if(pre[x]==0){
38             pre[x]=v;
39             p[x]=0;
40             q.push(x);
41         }
42         if(pre[y]==0){
43             pre[y]=v;
44             p[y]=1;
45             q.push(y);
46         }
47     }
48 }
49 
50 int main()
51 {   int T;scanf("%d",&T);
52     while(T--){
53         int tem;scanf("%d",&tem);
54         memset(p,0,sizeof(p));
55         memset(pre,0,sizeof(pre));
56         if(tem==1) printf("1\n");
57         else BFS(tem);
58         
59     }
60     return 0;
61 }