#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pip pair<int,pii>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define MOD 1000000007
typedef long long ll;
//int dx[]={1,-1,0,0};
//int dy[]={0,0,1,-1};
struct node
{
ll value;
int mod;
};
int visited[20000+10];
void bfs(int num)
{
queue<node> q;
node temp,hold,poss1,poss2;
temp.value=1LL;
temp.mod=(temp.value)%num;
if(temp.mod==0)
{
printf("%d\n",num);
return;
}
q.push(temp);
visited[temp.mod]=1;
while(!q.empty())
{
hold=q.front();
q.pop();
if(hold.mod==0)
{
printf("%lld\n",hold.value);
break;
}
poss1.value=hold.value;
poss1.value*=10;
poss1.mod=(poss1.value)%num;
if(!visited[poss1.mod])
{
visited[poss1.mod]=1;
q.push(poss1);
}
poss2.value=hold.value;
poss2.value*=10;
poss2.value+=1;
poss2.mod=(poss2.value)%num;
if(!visited[poss2.mod])
{
visited[poss2.mod]=1;
q.push(poss2);
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=0;i<20000+4;i++)
visited[i]=0;
bfs(n);
}
return 0;
}
CgogICAgI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAgICB1c2luZyBuYW1lc3BhY2Ugc3RkOwoKICAgICNkZWZpbmUgcGlpIHBhaXI8aW50LGludD4KICAgICNkZWZpbmUgcGlwIHBhaXI8aW50LHBpaT4KICAgICNkZWZpbmUgcGIgcHVzaF9iYWNrCiAgICAjZGVmaW5lIG1wIG1ha2VfcGFpcgogICAgI2RlZmluZSBmZiBmaXJzdAogICAgI2RlZmluZSBzcyBzZWNvbmQKICAgICNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKCiAgICB0eXBlZGVmIGxvbmcgbG9uZyBsbDsKICAgIC8vaW50IGR4W109ezEsLTEsMCwwfTsKICAgIC8vaW50IGR5W109ezAsMCwxLC0xfTsKCiAgICBzdHJ1Y3Qgbm9kZQogICAgewogICAgICAgIGxsIHZhbHVlOwogICAgICAgIGludCBtb2Q7CiAgICB9OwoKICAgIGludCB2aXNpdGVkWzIwMDAwKzEwXTsKCiAgICB2b2lkIGJmcyhpbnQgbnVtKQogICAgewogICAgICAgIHF1ZXVlPG5vZGU+IHE7CiAgICAgICAgbm9kZSB0ZW1wLGhvbGQscG9zczEscG9zczI7CgogICAgICAgIHRlbXAudmFsdWU9MUxMOwogICAgICAgIHRlbXAubW9kPSh0ZW1wLnZhbHVlKSVudW07CiAgICAgICAgaWYodGVtcC5tb2Q9PTApCiAgICAgICAgewogICAgICAgICAgICBwcmludGYoIiVkXG4iLG51bSk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CgogICAgICAgIHEucHVzaCh0ZW1wKTsKICAgICAgICB2aXNpdGVkW3RlbXAubW9kXT0xOwogICAgICAgIHdoaWxlKCFxLmVtcHR5KCkpCiAgICAgICAgewogICAgICAgICAgICBob2xkPXEuZnJvbnQoKTsKICAgICAgICAgICAgcS5wb3AoKTsKCiAgICAgICAgICAgIGlmKGhvbGQubW9kPT0wKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwcmludGYoIiVsbGRcbiIsaG9sZC52YWx1ZSk7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcG9zczEudmFsdWU9aG9sZC52YWx1ZTsKICAgICAgICAgICAgcG9zczEudmFsdWUqPTEwOwogICAgICAgICAgICBwb3NzMS5tb2Q9KHBvc3MxLnZhbHVlKSVudW07CiAgICAgICAgICAgIGlmKCF2aXNpdGVkW3Bvc3MxLm1vZF0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHZpc2l0ZWRbcG9zczEubW9kXT0xOwogICAgICAgICAgICAgICAgcS5wdXNoKHBvc3MxKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcG9zczIudmFsdWU9aG9sZC52YWx1ZTsKICAgICAgICAgICAgcG9zczIudmFsdWUqPTEwOwogICAgICAgICAgICBwb3NzMi52YWx1ZSs9MTsKCiAgICAgICAgICAgIHBvc3MyLm1vZD0ocG9zczIudmFsdWUpJW51bTsKICAgICAgICAgICAgaWYoIXZpc2l0ZWRbcG9zczIubW9kXSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgdmlzaXRlZFtwb3NzMi5tb2RdPTE7CiAgICAgICAgICAgICAgICBxLnB1c2gocG9zczIpOwogICAgICAgICAgICB9CgogICAgICAgIH0KCiAgICB9CgogICAgaW50IG1haW4oKQogICAgewogICAgICAgIGludCB0OwogICAgICAgIHNjYW5mKCIlZCIsJnQpOwogICAgICAgIHdoaWxlKHQtLSkKICAgICAgICB7CiAgICAgICAgICAgIGludCBuOwogICAgICAgICAgICBzY2FuZigiJWQiLCZuKTsKICAgICAgICAgICAgZm9yKGludCBpPTA7aTwyMDAwMCs0O2krKykKICAgICAgICAgICAgICAgIHZpc2l0ZWRbaV09MDsKCiAgICAgICAgICAgIGJmcyhuKTsKICAgICAgICB9CgogICAgICAgIHJldHVybiAwOwogICAgfQoK