#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int INF = 1e9;

int n,tests;
int dist[1<<20],best[1<<20],code[1024][1024];
int restore_sum[1<<20],restore_remainder[1<<20];
int cnt;
queue <int> q;
vector <int> v[1<<20];

void build_graph() {
  int i,j,z,next_sum,next_remainder;

  cnt=0;
  for(i=0;i<=n;i++) for(j=0;j<n;j++) {
    code[i][j]=++cnt;
    restore_sum[code[i][j]]=i;
    restore_remainder[code[i][j]]=j;
  }

  for(i=1;i<=cnt;i++) v[i].clear();

  for(i=0;i<=n;i++) for(j=0;j<n;j++) {
    for(z=0;z<=9;z++) {
      next_sum=i+z;
      next_remainder=j*10+z;
      next_remainder%=n;
      if((next_sum==i && next_remainder==j) || next_sum>n) continue;
      v[code[next_sum][next_remainder]].push_back(code[i][j]);
    }
  }
}

void bfs() {
  int i,curr,current_distance;

  while(!q.empty()) q.pop();
  for(i=1;i<=cnt;i++) dist[i]=INF;
  dist[code[n][0]]=0;

  q.push(code[n][0]);

  while(!q.empty()) {
    curr=q.front();
    q.pop();

    for(i=0;i<v[curr].size();i++) {
      current_distance=dist[curr]+1;
      if(dist[v[curr][i]]>current_distance) {
        dist[v[curr][i]]=current_distance;
        best[v[curr][i]]=restore_sum[curr]-restore_sum[v[curr][i]];
        q.push(v[curr][i]);
      }
      else if(dist[v[curr][i]]==current_distance) {
        best[v[curr][i]]=min(best[v[curr][i]],restore_sum[curr]-restore_sum[v[curr][i]]);
      }
    }
  }
}

int main() {
  //ios_base::sync_with_stdio(false);
  //cin.tie(NULL);
  //freopen("test.txt","r",stdin);
  int tests,sum,remainder,p;
  
  scanf("%d", &tests);
  while(tests--) {
    scanf("%d", &n);
    build_graph();
    bfs();
    sum=0;
    remainder=0;
    while(sum<n || remainder!=0) {
      p=best[code[sum][remainder]];
      printf("%d", p);
      sum+=p;
      remainder*=10;
      remainder+=p;
      remainder%=n;
    }
    printf("\n");
  } 
  
  return 0;
}