#include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<set> #include<map> #include<list> #include<queue> #include<vector> #define tree int o,int l,int r #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define lo o<<1 #define ro o<<1|1 #define ULL unsigned long long #define LL long long #define UI unsigned int #define inf 0x7fffffff #define eps 1e-7 #define M 29901 #define N 1000009 using namespace std; int T,n,m,k,t,maxv; struct Node { int c,last; } node[M]; bool res[N]; int main() { #ifndef ONLINE_JUDGE freopen("ex.in","r",stdin); #endif int ncase=0; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(node,-1,sizeof(node)); int ok=0; node[1].c=1; node[1].last=-1; queue<int>q; q.push(1); while(!q.empty()) { int yu=q.front(); q.pop(); for(int i=0; i<2; i++) { int tp=(yu*10+i)%n; if(node[tp].c==-1) { node[tp].c=i; node[tp].last=yu; if(tp==0)//只找第一个,肯定是最小的！ { ok=1; break; } q.push(tp); } } if(ok)break; } int sub=0,top=0; while(sub!=-1) { res[top++]=node[sub].c; sub=node[sub].last; } for(int i=top-1; i>=0; i--) printf("%d",res[i]); puts(""); } return 0; }