/*
written by- Piyush Golani
language- c++
country- India
College- N.I.T Jamshedpur
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<cctype>
#include<queue>
using namespace std;
#define pb push_back
#define all(s) s.begin(),s.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=b;i--)
#define PI 3.1415926535897932384626433832795
#define INF 1000000005
#define BIG_INF 7000000000000000000LL
#define mp make_pair
#define eps 1e-9
#define LL long long
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007
bool visited[20005];
int main()
{
int t;
si(t);
while(t--)
{
LL n;
sll(n);
memset(visited,false,sizeof(visited));
queue<LL> Q;
Q.push(1);
while(!Q.empty())
{
LL p= Q.front();
Q.pop();
if(visited[p%n]==1) continue;
visited[p%n]=1;
if(p%n==0)
{
printf("%lld\n",p);
break;
}
Q.push(p*10);
Q.push(p*10+1);
}
}
return 0;
}
LyoKd3JpdHRlbiBieS0gUGl5dXNoIEdvbGFuaQpsYW5ndWFnZS0gYysrCmNvdW50cnktIEluZGlhCkNvbGxlZ2UtIE4uSS5UIEphbXNoZWRwdXIKKi8KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxzc3RyZWFtPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPG1hcD4KI2luY2x1ZGU8Y2N0eXBlPgojaW5jbHVkZTxxdWV1ZT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBhbGwocykgcy5iZWdpbigpLHMuZW5kKCkKI2RlZmluZSBmKGksYSxiKSBmb3IoaW50IGk9YTtpPGI7aSsrKQojZGVmaW5lIEYoaSxhLGIpIGZvcihpbnQgaT1hO2k+PWI7aS0tKQojZGVmaW5lIFBJIDMuMTQxNTkyNjUzNTg5NzkzMjM4NDYyNjQzMzgzMjc5NQojZGVmaW5lIElORiAxMDAwMDAwMDA1CiNkZWZpbmUgQklHX0lORiA3MDAwMDAwMDAwMDAwMDAwMDAwTEwKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBlcHMgMWUtOQojZGVmaW5lIExMIGxvbmcgbG9uZwojZGVmaW5lIHNpKG4pIHNjYW5mKCIlZCIsJm4pCiNkZWZpbmUgc2xsKG4pIHNjYW5mKCIlbGxkIiwmbikKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwoKCgpib29sIHZpc2l0ZWRbMjAwMDVdOwoKCmludCBtYWluKCkKewogICAgaW50IHQ7CiAgICBzaSh0KTsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBMTCBuOwogICAgICAgIHNsbChuKTsKICAgICAgICBtZW1zZXQodmlzaXRlZCxmYWxzZSxzaXplb2YodmlzaXRlZCkpOwogICAgICAgIHF1ZXVlPExMPiBROwogICAgICAgIFEucHVzaCgxKTsKICAgICAgICB3aGlsZSghUS5lbXB0eSgpKQogICAgICAgIHsKICAgICAgICAgICAgTEwgcD0gUS5mcm9udCgpOwogICAgICAgICAgICBRLnBvcCgpOwogICAgICAgICAgICBpZih2aXNpdGVkW3Albl09PTEpIGNvbnRpbnVlOwogICAgICAgICAgICB2aXNpdGVkW3Albl09MTsKICAgICAgICAgICAgaWYocCVuPT0wKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwcmludGYoIiVsbGRcbiIscCk7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgICAgICBRLnB1c2gocCoxMCk7CiAgICAgICAgICAgIFEucHVzaChwKjEwKzEpOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9Cg==