You are given an integer N. Can you find the least positive integer X made up of only 9's and 0's, such that, X is a multiple of N?

Update  

X is made up of one or more occurences of 9 and zero or more occurences of 0. 

Input Format 

The first line contains an integer T which denotes the number of test cases. T lines follow. 

Each line contains the integer N for which the solution has to be found.

Output Format 

Print the answer X to STDOUT corresponding to each test case. The output should not contain any leading zeroes. 

Constraints 

1 <= T <= 10^{4} 

1 <= N <= 500

Sample Input  

3
5
7
1

Sample Output  

90
9009
9

Explanation 

90 is the smallest number made up of 9's and 0's divisible by 5. 
Similarly, you can derive for other cases. 

Timelimits
Timelimits for this challenge is given here

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
__author__ = 'bozo'
import sys
T = int(sys.stdin.readline())
for i in range(0, T):
	n = int(sys.stdin.readline())
	k = 1
	while int(str(bin(k))[2:].replace('1', '9')) % n != 0:
		k += 1
	print(int(str(bin(k))[2:].replace('1', '9')))


import sys
a = 0

def check(r, n):
	for e in r:
		if int(int(e) / n) * n == e:
			print(e)
			return True
	return False

def genNew(r):
	result = []
	for e in r:
		e1 = e * 10
		e2 = e * 10 + 9
		result.append(e1)
		result.append(e2)
	return result

def Find(r, n):
	if check(r, n) == True:
		return 0
	else:
		r2 = genNew(r)
		Find(r2, n)
for line in sys.stdin:
	if a == 0:
		a = a + 1
		continue
	else:
		Find([9], int(line))


import sys

def s(n):
	i = 1
	while True:
		v = int(bin(i)[2:].replace('1', '9'))
		if v % n == 0:
			return v
		i += 1
T = int(sys.stdin.readline())
for i in range(0, T):
	n = int(sys.stdin.readline())
	print(s(n))


def solve(n):
	number_of_digits = 1
	power_of_ten = 10
	candidates = []
	answers = []
	for digit in range(10):
		if digit * n % 10 in (0, 9):
			candidates.append(digit)
	while True:
		new_candidates = []
		for candidate in candidates:
			for digit in range(10):
				new_candidate = digit * power_of_ten + candidate
				product = new_candidate * n
				if product // power_of_ten % 10 in (0, 9):
					if product != 0 and all((digit in '09' for digit in str(product))):
						answers.append(product)
					new_candidates.append(new_candidate)
		if answers:
			return min(answers)
		candidates = new_candidates
		power_of_ten *= 10
cached_answers = [0]
for n in range(1, 501):
	cached_answers.append(solve(n))
from sys import stdin
T = int(stdin.readline())
for _ in range(T):
	print(cached_answers[int(stdin.readline())])


from math import floor, ceil, log

def candidate(i):
	return int(bin(i)[2:].replace('1', '9'))

def leastPositive90(X):
	i = 1
	done = False
	while not done:
		N = candidate(i)
		if N >= X and N % X == 0:
			return N
		i += 1
n = int(input())
for i in range(n):
	X = int(input())
	print(leastPositive90(X))


def mult(a, b):
	return a % b == 0

def lcm(n):
	ls = [0]
	output = []
	while True:
		for e in ls:
			outputs = []
			if e % n == 0 and e > 0:
				output.append(e)
		if len(output) > 0:
			return min(output)
		ls = list(map(lambda x: 10 * x, ls)) + list(map(lambda x: 10 * x + 9, ls))
for i in range(int(input())):
	print(lcm(int(input())))


def getNextNum(curr):
	if curr % 2 == 0:
		return curr + 9
	else:
		string = str(curr)
		string = string[:1] + '00'
		return int(string)

def getNextSet(l):
	newSet = []
	for n in l:
		newSet.append(int(str(n) + '0'))
		newSet.append(int(str(n) + '9'))
	return newSet

def calcX(num):
	listOfNines = [[9]]
	if listOfNines[0][0] % num == 0:
		return listOfNines[0][0]
	i = 0
	while True:
		listOfNines.append(getNextSet(listOfNines[i]))
		for j in listOfNines[i]:
			if j % num == 0:
				return j
		i = i + 1
inputNums = []
numInputs = int(input())
i = 0
while i < numInputs:
	inputNums.append(int(input()))
	i = i + 1
for num in inputNums:
	print(calcX(num))


import fileinput

def to_special(x):
	if x == 0:
		return '0'
	string = ''
	while x > 0:
		if x & 1 == 1:
			string = '9' + string
		else:
			string = '0' + string
		x = x >> 1
	return int(string)

def find_special_multiple(n):
	i = 1
	multiple = to_special(i)
	while multiple % n != 0:
		i = i + 1
		multiple = to_special(i)
	return multiple
for line in fileinput.input():
	if not fileinput.isfirstline():
		print(find_special_multiple(int(line)))


cases = int(input())
for _ in range(cases):
	n = int(input())
	i = 1
	while True:
		num = int(bin(i)[2:].replace('1', '9'))
		if num % n == 0:
			print(num)
			break
		i += 1


from sys import stdin
from itertools import *
ans = [None] * 501
nfound = 0
d = 0
while nfound < 500:
	d += 1
	for rest in list(product(*tuple(((0, 9 * 10 ** i) for i in range(d - 2, -1, -1))))):
		n = 9 * 10 ** (d - 1) + sum(rest)
		for i in range(1, 501):
			if not ans[i] and 0 == n % i:
				ans[i] = n
				nfound += 1
T = int(stdin.readline())
for _ in range(T):
	N = int(stdin.readline())
	print(ans[N])


l = [9, 90, 99, 900, 909, 999, 990, 9000, 9009, 9099, 9090, 9900, 9909, 9990, 9999, 90000, 99000, 99009, 99099, 99090, 99900, 99909, 99990, 99999, 90000, 90009, 90099, 90090, 90900, 90909, 90990, 90999, 990000, 999000, 999009, 999099, 999090, 999900, 999909, 999990, 999999, 990000, 990009, 990099, 990090, 990900, 990909, 990990, 990999, 900000, 909000, 909009, 909099, 909090, 909900, 909909, 909990, 909999, 900000, 900009, 900099, 900090, 900900, 900909, 900990, 900999]
t = int(input())
for i in range(t):
	chk = 1
	y = [9]
	m = []
	n = int(input())
	while chk:
		for k in y:
			m.append(k * 10)
			m.append(k * 10 + 9)
			if k % n == 0:
				print(k)
				chk = 0
				break
		y = m
		y.sort()
		m = []


from collections import deque
t = int(input())
tmp = '90'
for i in range(0, t):
	n = int(input())
	Q = deque()
	Q.append('9')
	while Q:
		t = Q.popleft()
		if int(t) % n == 0:
			print(t)
			break
		Q.append(t + '0')
		Q.append(t + '9')


import math
import sys

def find(N):
	A = [9]
	print(f(N, A))

def f(N, A):
	size = 1
	i = 0
	while size > i:
		m = A[i]
		if m % N == 0:
			return m
		else:
			A.append(m * 10)
			A.append(m * 10 + 9)
			size = size + 2
		i = i + 1
T = int(input())
while T > 0:
	N = int(input())
	find(N)
	T = T - 1


def answer(n, debug=False):
	residues = [(-1, -1)] * n
	res = 9 % n
	residues[res] = (1, 0)
	for digNo in range(2, n + 1):
		res = res * 10 % n
		residues = [(digNo, (i - res) % n) if residues[(i - res) % n][0] != -1 and residues[i][0] == -1 else residues[i] for i in range(n)]
		if residues[res][0] == -1:
			residues[res] = (digNo, 0)
		if residues[0][0] != -1:
			break
	i = 0
	ans = 9 * 10 ** (residues[i][0] - 1)
	while residues[i][1] != 0:
		i = residues[i][1]
		ans += 9 * 10 ** (residues[i][0] - 1)
	return ans
t = int(input())
for i in range(t):
	print(answer(int(input())))


import fileinput

def nums_made_of_nine_and_zero_for_digits(digits):
	if digits == 1:
		yield '0'
		yield '9'
		return
	for zeros in range(digits - 2, -1, -1):
		for tail in nums_made_of_nine_and_zero_for_digits(digits - zeros - 1):
			yield ('9' + '0' * zeros + tail)

def nums_made_of_nine_and_zero():
	yield 9
	digits = 2
	while True:
		for num in nums_made_of_nine_and_zero_for_digits(digits):
			yield int(num)
		digits += 1

def min_spec_mul(n):
	for num in nums_made_of_nine_and_zero():
		if num % n == 0:
			return num
is_first = True
for line in fileinput.input():
	if is_first:
		is_first = False
		continue
	print(min_spec_mul(int(line)))


def special_multiples():
	yield 9
	last_depth = [9]
	current_depth = []
	while len(last_depth) < 20:
		for x in last_depth:
			current_depth += [x * 10, x * 10 + 9]
			yield (x * 10)
			yield (x * 10 + 9)
		last_depth = current_depth

def get_multiple(n):
	for m in special_multiples():
		if m % n == 0:
			return m
t = int(input())
for i in range(t):
	n = int(input())
	print(get_multiple(n))


import sys
from copy import copy

def try_to_find_zero(l, modulus, current_total, used_nums):
	if current_total == 0:
		return used_nums
	if len(l) == 0:
		return False
	useit = try_to_find_zero(l[:-1], modulus, (current_total + l[-1]) % modulus, used_nums)
	loseit = try_to_find_zero(l[:-1], modulus, current_total, used_nums)
	if useit == False and loseit == False:
		return False
	elif useit == False:
		return loseit
	elif loseit == False:
		a = copy(useit)
		a.append(len(l) - 1)
		return a
	else:
		return loseit
data_set = [int(i.strip()) for i in sys.stdin.readlines()[1:]]
for num in data_set:
	possible_vals = []
	a = False
	while a == False:
		possible_vals.append(9 * 10 ** len(possible_vals) % num)
		a = try_to_find_zero(possible_vals[:-1], num, possible_vals[-1], [len(possible_vals) - 1])
	answer = sum(map(lambda x: 9 * 10 ** x, a))
	print(answer)


__author__ = 'mnganesh'

class NumberFactory:

	def __init__(self):
		self.num = 0

	def reset(self):
		self.num = 0

	def next(self):
		self.num += 1
		num = self.num
		return int(bin(num)[2:].replace('1', '9'))

def compute(n, numberFactory):
	x = numberFactory.next()
	while x % n != 0:
		x = numberFactory.next()
	return x
nCases = int(input())
numFact = NumberFactory()
for i in range(nCases):
	number = int(input())
	numFact.reset()
	print(compute(number, numFact))


from itertools import product

def generate():
	return (int(''.join(i)) for i in product('09', repeat=20))
from sys import stdin
inpu = stdin.readlines()
for i in range(1, int(inpu[0]) + 1):
	no = int(inpu[i])
	li = generate()
	li.__next__()
	for digi in li:
		if not digi % no:
			print(digi)
			break


t = int(input())
for i in range(0, t):
	s = [0, 9]
	n = int(input())
	j = 1
	while 1:
		if s[j] % n != 0:
			s.insert(2 * j, s[j] * 10)
			s.insert(2 * j + 1, s[j] * 10 + 9)
			j = j + 1
		elif s[j] % n == 0:
			print(s[j])
			break


MAX_N = 500
MAX_SEARCH = 10000
not_found = list(range(1, MAX_N + 1))
found = {}

def to_ninary(n):
	result = 0
	digits = bin(n)[2:]
	l = len(digits)
	for i in range(0, l):
		result *= 10
		if digits[i] == '1':
			result += 9
	return result
for n in range(1, MAX_SEARCH):
	test = to_ninary(n)
	to_remove = []
	for nf in not_found:
		if test % nf == 0:
			to_remove.append(nf)
			found[nf] = test
	for r in to_remove:
		not_found.remove(r)
t = int(input())
while t > 0:
	print(found[int(input())])
	t -= 1


def candidate_generator():
	candidate = ['0']
	while True:
		digits = len(candidate)
		if candidate.count('9') == digits:
			candidate = ['0'] * digits + ['9']
		else:
			first_0_idx = candidate.index('0')
			candidate = ['0'] * first_0_idx + ['9'] + candidate[first_0_idx + 1:]
		yield int(''.join(reversed(candidate)))

def find_special_multiple(n):
	for candidate in candidate_generator():
		if candidate % n == 0:
			return candidate

def main():
	test_num = int(input())
	for i in range(test_num):
		n = int(input())
		print(find_special_multiple(n))
main()


t = int(input())
for i in range(0, t):
	z = int(input())
	g = 1
	while True:
		h = int(bin(g)[2:])
		if h * 9 % z == 0:
			print(h * 9)
			break
		g += 1


from itertools import product

def generate():
	return (int(''.join(i)) for i in product('09', repeat=20))
from sys import stdin
inpu = stdin.readlines()
for i in range(1, int(inpu[0]) + 1):
	no = int(inpu[i])
	il = generate()
	il.__next__()
	for digit in il:
		if not digit % no:
			print(digit)
			break


n = int(input())
for i in range(0, n):
	d = int(input())
	c = 2
	f = 9
	while f % d != 0:
		l = str(bin(c))
		c = str(c)
		l = str(l)
		l = l[2:len(l)]
		l = int(l)
		f = l * 9
		c = int(c)
		c = c + 1
	print(f)


t = int(input())
while t > 0:
	m = int(input())
	a = []
	a.append(9)
	while 1:
		b = a.pop(0)
		c = b % m
		if c == 0:
			break
		else:
			a.append(b * 10)
			a.append(b * 10 + 9)
	print(b)
	t = t - 1


from itertools import product

def generate():
	return (int(''.join(i)) for i in product('09', repeat=20))
from sys import stdin
inpu = stdin.readlines()
for i in range(1, int(inpu[0]) + 1):
	no = int(inpu[i])
	il = generate()
	il.__next__()
	for digit in il:
		if not digit % no:
			print(digit)
			break


def nextNum(number):
	global numbers
	numberList = list(str(number))
	numberList.reverse()
	if '0' in numberList:
		dig = numberList.index('0')
		for i in range(dig):
			numberList[i] = '0'
		numberList[dig] = '9'
	else:
		numberList = list('0' * len(numberList))
		numberList.append('9')
	numberList.reverse()
	N = int(''.join(numberList))
	numbers.append(N)
	return N

def search(N):
	for number in numbers:
		if number % N == 0:
			return number
	K = numbers[-1]
	while K % N != 0:
		K = nextNum(K)
	return K

def main():
	global numbers
	numbers = [9, 90, 99, 900, 909, 990, 999, 9000, 9009, 9090, 9099, 9900, 9909, 9990, 9999, 90000, 90009, 90090, 90099, 90900, 90909, 90990, 90999, 99000, 99009, 99090, 99099, 99900, 99909, 99990, 99999, 900000, 900009, 900090, 900099, 900900, 900909, 900990, 900999, 909000, 909009, 909090, 909099, 909900, 909909, 909990, 909999, 990000, 990009, 990090, 990099, 990900, 990909, 990990, 990999, 999000, 999009, 999090, 999099, 999900, 999909, 999990, 999999, 9000000, 9000009, 9000090, 9000099, 9000900, 9000909, 9000990, 9000999, 9009000, 9009009, 9009090, 9009099, 9009900, 9009909, 9009990, 9009999, 9090000, 9090009, 9090090, 9090099, 9090900, 9090909, 9090990, 9090999, 9099000, 9099009, 9099090, 9099099, 9099900, 9099909, 9099990, 9099999, 9900000, 9900009, 9900090, 9900099, 9900900, 9900909, 9900990, 9900999, 9909000, 9909009, 9909090, 9909099, 9909900, 9909909, 9909990, 9909999, 9990000, 9990009, 9990090, 9990099, 9990900, 9990909, 9990990, 9990999, 9999000, 9999009, 9999090, 9999099, 9999900, 9999909, 9999990, 9999999, 90000000, 90000009, 90000090, 90000099, 90000900, 90000909, 90000990, 90000999, 90009000, 90009009, 90009090, 90009099, 90009900, 90009909, 90009990, 90009999, 90090000, 90090009, 90090090, 90090099, 90090900, 90090909, 90090990, 90090999, 90099000, 90099009, 90099090, 90099099, 90099900, 90099909, 90099990, 90099999, 90900000, 90900009, 90900090, 90900099, 90900900, 90900909, 90900990, 90900999, 90909000, 90909009, 90909090, 90909099, 90909900, 90909909, 90909990, 90909999, 90990000, 90990009, 90990090, 90990099, 90990900, 90990909, 90990990, 90990999, 90999000, 90999009, 90999090, 90999099, 90999900, 90999909, 90999990, 90999999, 99000000, 99000009, 99000090, 99000099, 99000900, 99000909, 99000990, 99000999, 99009000, 99009009, 99009090, 99009099, 99009900, 99009909, 99009990, 99009999, 99090000, 99090009, 99090090, 99090099, 99090900, 99090909, 99090990, 99090999, 99099000, 99099009, 99099090, 99099099, 99099900, 99099909, 99099990, 99099999, 99900000, 99900009, 99900090, 99900099, 99900900, 99900909, 99900990, 99900999, 99909000, 99909009, 99909090, 99909099, 99909900, 99909909, 99909990, 99909999, 99990000, 99990009, 99990090, 99990099, 99990900, 99990909, 99990990, 99990999, 99999000, 99999009, 99999090, 99999099, 99999900, 99999909, 99999990, 99999999, 900000000, 900000009, 900000090, 900000099, 900000900, 900000909, 900000990, 900000999, 900009000, 900009009, 900009090, 900009099, 900009900, 900009909, 900009990, 900009999, 900090000, 900090009, 900090090, 900090099, 900090900, 900090909, 900090990, 900090999, 900099000, 900099009, 900099090, 900099099, 900099900, 900099909, 900099990, 900099999, 900900000, 900900009, 900900090, 900900099, 900900900, 900900909, 900900990, 900900999, 900909000, 900909009, 900909090, 900909099, 900909900, 900909909, 900909990, 900909999, 900990000, 900990009, 900990090, 900990099, 900990900, 900990909, 900990990, 900990999, 900999000, 900999009, 900999090, 900999099, 900999900, 900999909, 900999990, 900999999, 909000000, 909000009, 909000090, 909000099, 909000900, 909000909, 909000990, 909000999, 909009000, 909009009, 909009090, 909009099, 909009900, 909009909, 909009990, 909009999, 909090000, 909090009, 909090090, 909090099, 909090900, 909090909, 909090990, 909090999, 909099000, 909099009, 909099090, 909099099, 909099900, 909099909, 909099990, 909099999, 909900000, 909900009, 909900090, 909900099, 909900900, 909900909, 909900990, 909900999, 909909000, 909909009, 909909090, 909909099, 909909900, 909909909, 909909990, 909909999, 909990000, 909990009, 909990090, 909990099, 909990900, 909990909, 909990990, 909990999, 909999000, 909999009, 909999090, 909999099, 909999900, 909999909, 909999990, 909999999, 990000000, 990000009, 990000090, 990000099, 990000900, 990000909, 990000990, 990000999, 990009000, 990009009, 990009090, 990009099, 990009900, 990009909, 990009990, 990009999, 990090000, 990090009, 990090090, 990090099, 990090900, 990090909, 990090990, 990090999, 990099000, 990099009, 990099090, 990099099, 990099900, 990099909, 990099990, 990099999, 990900000, 990900009, 990900090, 990900099, 990900900, 990900909, 990900990, 990900999, 990909000, 990909009, 990909090, 990909099, 990909900, 990909909, 990909990, 990909999, 990990000, 990990009, 990990090, 990990099, 990990900, 990990909, 990990990, 990990999, 990999000, 990999009, 990999090, 990999099, 990999900, 990999909, 990999990, 990999999, 999000000, 999000009, 999000090, 999000099, 999000900, 999000909, 999000990, 999000999, 999009000, 999009009, 999009090, 999009099, 999009900, 999009909, 999009990, 999009999, 999090000, 999090009, 999090090, 999090099, 999090900, 999090909, 999090990, 999090999, 999099000, 999099009, 999099090, 999099099, 999099900, 999099909, 999099990, 999099999, 999900000, 999900009, 999900090, 999900099, 999900900, 999900909, 999900990, 999900999, 999909000, 999909009, 999909090, 999909099, 999909900, 999909909, 999909990, 999909999, 999990000, 999990009, 999990090, 999990099, 999990900, 999990909, 999990990, 999990999, 999999000, 999999009, 999999090, 999999099, 999999900, 999999909, 999999990, 999999999, 9000000000]
	T = int(input())
	for i in range(T):
		N = int(input())
		print(search(N))
	return 0
main()


def nineUp(x):
	y = bin(x)[2:]
	r = ''
	for i in y:
		if i == '0':
			r = r + '0'
		else:
			r = r + '9'
	return int(r)
x = int(input())
for i in range(x):
	num = int(input())
	i = 1
	while True:
		z = nineUp(i)
		if z % num == 0:
			print(z)
			break
		i = i + 1


import sys
m = {}
for n in range(1, 5000):
	x = int(format(n, 'b')) * 9
	for d in range(1, 501):
		if x % d == 0:
			if not d in m:
				m[d] = x
T = int(sys.stdin.readline())
for t in range(T):
	n = int(sys.stdin.readline())
	print(m[n])


table = [0] * 500
c = 0

def spcNum(n):
	return int(bin(n)[2:]) * 9
g = 1
while c < 500:
	genNum = spcNum(g)
	for i in range(500):
		if genNum % (i + 1) == 0:
			if table[i] == 0:
				table[i] = genNum
				c += 1
			if genNum // (i + 1) <= 500 and table[genNum // (i + 1) - 1] == 0:
				table[genNum // (i + 1) - 1] = genNum
				c += 1
	g += 1
for t in range(int(input())):
	print(table[int(input()) - 1])


import sys
numbers = []

def generate_nums(n):
	numbers.append(n)
	q = [n]
	while len(str(q[0])) < 13:
		current = q[0] * 10
		q.pop(0)
		q.append(current)
		numbers.append(current)
		q.append(current + 9)
		numbers.append(current + 9)
T = int(sys.stdin.readline())
generate_nums(9)
for t in range(T):
	N = int(sys.stdin.readline())
	for n in numbers:
		if n % N == 0:
			print(n)
			break


def nz(l, x, n=0):
	if x >= 0:
		nz(l, x - 1, n + 9 * 10 ** x)
		nz(l, x - 1, n)
	else:
		l.append(n)

def main():
	T = int(input())
	l = []
	nz(l, 12)
	l.pop()
	l.sort()
	for i in range(T):
		x = int(input())
		for j in l:
			if j % x == 0:
				print(j)
				break
main()


from queue import PriorityQueue

def get_least_multiple(n):
	pq = PriorityQueue()
	pq.put(9)
	while True:
		cur = pq.get()
		if cur % n == 0:
			return cur
		pq.put(cur * 10)
		pq.put(cur * 10 + 9)
arr = [get_least_multiple(i) for i in range(1, 501)]
ts = int(input())
for t in range(ts):
	n = int(input())
	print(arr[n - 1])


Multiple = []
powerNum = 1
currentNum = 9
currentPowerNum = -1
i = 0
while i < 100000:
	Multiple.append(0)
	i += 1
Multiple[0] = 9
Multiple[1] = 90
index = 2
start = 0
end = 0
curVal = 90
while index < 10000:
	while start <= end:
		Multiple[index] = curVal + Multiple[start]
		start += 1
		index += 1
	curVal = curVal * 10
	start = 0
	end = index - 1
	Multiple[index] = curVal
	index += 1
T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	i = 0
	while i < 10000:
		if Multiple[i] % N == 0:
			print(Multiple[i])
			break
		i += 1


i = 1
R = [-1] * 501
while i <= 10000:
	X = 0
	for j in range(31, -1, -1):
		X *= 10
		if i & 1 << j > 0:
			X += 9
	for j in range(1, 501):
		if R[j] != -1:
			continue
		if X % j == 0:
			R[j] = X
	i += 1
T = int(input())
for _ in range(T):
	N = int(input())
	print(R[N])


q = int(input())
for w in range(q):
	n = int(input())
	for i in range(1, 2 ** 50):
		a = bin(i)
		if int(a[2:]) * 9 % n == 0:
			print(int(a[2:]) * 9)
			break


def nines_and_zeros():
	num = 1
	while True:
		yield int(bin(num)[2:].replace('1', '9'))
		num += 1

def least_ninezero(num):
	for guess in nines_and_zeros():
		if not guess % num:
			return guess
count = int(input())
for _ in range(count):
	print(least_ninezero(int(input())))


import sys
f = sys.stdin

def check(maxm, minm, dig, i, n):
	minm = minm + 10 ** i * 9
	if minm % n == 0:
		print(minm)
		return 1
	fminm = minm
	for j in range(i):
		fminm = minm + 10 ** j * 9
		if fminm % n == 0:
			print(fminm)
			return 1
		for m in range(j):
			k = check(maxm, fminm, dig, m, n)
			if k == 1:
				return 1
	return 0
t = int(input())
for i in range(t):
	n = int(input())
	num = 9
	f = 0
	dig = 1
	while True:
		if num % n == 0:
			print(num)
			break
		else:
			lnum = 0
			f = 0
			for i in range(dig):
				lnum = lnum + 10 ** i * 9
			i = 0
			ffknum = num
			fknum = num
			while lnum != fknum:
				f = check(lnum, ffknum, dig, i, n)
				fknum = fknum + 10 ** i * 9
				if f == 1:
					break
				i += 1
			if f == 1:
				break
			dig += 1
			num = 10 ** (dig - 1) * 9
	t += 1


def main():
	T = int(input())
	NX = {}
	for i in range(T):
		N = int(input())
		if N in NX:
			print(NX[N])
			continue
		k = 1
		while True:
			X = conv(k)
			if X % N == 0:
				print(X)
				NX[N] = X
				break
			k += 1

def conv(b):
	exp = 1
	num = 0
	while b:
		num += 9 * exp * (b & 1)
		b >>= 1
		exp *= 10
	return num
main()


import sys

def is_divisible(m, n):
	return m % n == 0

def bin_str(i):
	if i == 0:
		return '0'
	s = ''
	while i:
		if i & 1 == 1:
			s = '1' + s
		else:
			s = '0' + s
		i >>= 1
	return s

def find_min_div(n):
	i = 1
	while True:
		m = int(bin_str(i).replace('1', '9'))
		if is_divisible(m, n):
			return m
		i += 1
firstline = True
for line in sys.stdin:
	n = int(line.rstrip('\n'))
	if firstline:
		firstline = False
	else:
		print(find_min_div(n))


getBin = lambda x: x >= 0 and str(bin(x))[2:] or '-' + str(bin(x))[3:]
T = int(input())
for t in range(T):
	n = input()
	sol = '9' + '0' * (len(n) - 1) if int(n) >= 10 else '9'
	while int(sol) % int(n) != 0:
		sol = sol.replace('9', '1')
		sol = int(sol, 2) + 1
		sol = getBin(sol).replace('1', '9')
	print(sol)


import fileinput
import fractions
import itertools

def is_ok(n, x):
	return fractions.gcd(n, x) == n
lines = [line for line in fileinput.input()]
lines = lines[1:]
for line in lines:
	numbers = (int(bin(n)[2:].replace('1', '9')) for n in itertools.count(1))
	for x in numbers:
		if is_ok(int(line), x):
			print(x)
			break


t = int(input())
co = 0
while t > co:
	n = int(input())
	for i in range(1, 65536):
		b = bin(i)
		st = b.lstrip('0b')
		a = st
		c = a.replace('1', '9')
		k = int(c)
		if k % n == 0:
			print(k)
			break
	co = co + 1


t = int(input())
for c in range(t):
	N = int(input())
	i = 0
	while True:
		i += 1
		bini = int(bin(i)[2:]) * 9
		if bini % N == 0:
			print(bini)
			break


testcase = int(input())
for x in range(testcase):
	num = int(input())
	flag = 1
	while int(str(bin(flag))[2:].replace('1', '9')) % num != 0:
		flag += 1
	print(int(str(bin(flag))[2:].replace('1', '9')))


def g(n):
	k = [-1] * n
	r = l = 1
	k[1 % n] = 1
	for i in range(1, n + 1):
		r = r * 10 % n
		l <<= 1
		for j in range(1, n):
			if k[j] != -1 and k[j] < l and (k[(r + j) % n] > k[j] + l or k[(r + j) % n] == -1):
				k[(r + j) % n] = k[j] + l
		if k[r] == -1:
			k[r] = l
		if k[0] != -1:
			return k[0]
	return k[0]

def f(k):
	for i in range(2):
		if k % 3 == 0:
			k = k // 3
		else:
			break
	return 9 * int(bin(g(k))[2:])
for t in range(int(input())):
	print(f(int(input())))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	x = 1
	while int(str(bin(x))[2:].replace('1', '9')) % N != 0:
		x += 1
	print(int(str(bin(x))[2:].replace('1', '9')))


t = int(input())
for i in range(t):
	n = int(input())
	j = 1
	while 1:
		b = bin(j).replace('1', '9')
		m = int(b[2:])
		if m % n == 0:
			break
		else:
			j += 1
	print(m)


T = int(input())
for t in range(T):
	N = int(input())
	i = 1
	while int('{:b}'.format(i).replace('1', '9')) % N != 0:
		i += 1
	print('{:b}'.format(i).replace('1', '9'))


from itertools import permutations, count
nums = ['0', '9']

def smallest_9_0(n):
	for x in count(1):
		number = int(bin(x)[2:].replace('1', '9'))
		if not number % n:
			return number
for case in range(int(input())):
	print(smallest_9_0(int(input())))


T = input()
T = int(T)
for t in range(T):
	n = input()
	n = int(n)
	if n == 0:
		print(0)
		continue
	temp = 1
	while int(str(bin(temp)[2:]).replace('1', '9')) % n != 0 and temp != 0:
		temp += 1
	print(bin(temp)[2:].replace('1', '9'))


t = int(input())
for _ in range(t):
	n = int(input())
	i = 1
	tmp = -1
	while True:
		tmp = int('{0:b}'.format(i).replace('1', '9'))
		if tmp % n == 0:
			break
		else:
			i += 1
	print(tmp)


from itertools import product as prod

def fn(n):
	d = 1
	while 1:
		for r in prod('09', repeat=d):
			if r[0] == '9' and int(''.join(r)) % n == 0:
				return ''.join(r)
		d += 1
for i in range(int(input())):
	n = int(input())
	print(fn(n))


for t in range(0, int(input())):
	n = int(input())
	i = 1
	while int(str(bin(i))[2:].replace('1', '9')) % n != 0:
		i += 1
	ans = str(bin(i))[2:].replace('1', '9')
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	x = 1
	while True:
		y = bin(x).replace('0b', '').replace('1', '9')
		if int(y) % n == 0:
			print(y)
			break
		x += 1


for i in range(int(input())):
	n = int(input())
	j = 1
	while int(str(bin(j))[2:].replace('1', '9')) % n != 0:
		j += 1
	s = str(bin(j))[2:].replace('1', '9')
	print(s)


def my_bin(n):
	return str(bin(n))[2:]

def my_number(b):
	b = b.replace('1', '9')
	return int(b)
nums = []
for t in range(int(input())):
	nums.append(int(input()))
copy = nums[:]
res = {}
i = 1
while copy:
	m = my_number(my_bin(i))
	remove = []
	for num in copy:
		if m % num == 0:
			res[num] = m
			remove.append(num)
	for num in remove:
		copy.remove(num)
	i += 1
for num in nums:
	print(res[num])


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	x = 1
	while int(str(bin(x))[2:].replace('1', '9')) % N != 0:
		x += 1
	print(int(str(bin(x))[2:].replace('1', '9')))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	x = 1
	while int(str(bin(x))[2:].replace('1', '9')) % N != 0:
		x += 1
	print(int(str(bin(x))[2:].replace('1', '9')))


import itertools
t = int(input())
for i in range(t):
	n = int(input())
	temp = 1
	flag = False
	val = 0
	while True:
		tempBin = [''.join(seq) for seq in itertools.product('09', repeat=temp)]
		for i in tempBin:
			if int(i) % n == 0 and int(i) != 0:
				flag = True
				val = int(i)
				break
		if flag == True:
			break
		temp += 1
	print(val)


to_test = set(range(1, 501))
done = {}
l = ['9']
while True:
	s = l[0]
	if len(to_test) == 0:
		break
	l = l[1:]
	l.append(s + '0')
	l.append(s + '9')
	N = int(s)
	done_now = set()
	for x in to_test:
		if N % x == 0:
			done_now.add(x)
			done[x] = N
	to_test = to_test - done_now
t = int(input())
for i in range(t):
	print(done[int(input())])


t = int(input())
for _ in range(t):
	N = int(input())
	i = 1
	while int(str(bin(i)[2:]).replace('1', '9')) % N != 0:
		i += 1
	print(int(str(bin(i)[2:]).replace('1', '9')))


l = []
for i in range(1000000):
	l.append(int(bin(i + 1)[2:]) * 9)
for t in range(int(input())):
	i = 0
	n = int(input())
	while l[i] % n > 0:
		i += 1
	print(l[i])


T = int(input())
for _ in range(T):
	N = int(input())
	x = 1
	while int(str(bin(x))[2:].replace('1', '9')) % N != 0:
		x += 1
	print(int(str(bin(x))[2:].replace('1', '9')))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	x = 1
	while int(str(bin(x))[2:].replace('1', '9')) % N != 0:
		x += 1
	print(int(str(bin(x))[2:].replace('1', '9')))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	x = 1
	while int(str(bin(x))[2:].replace('1', '9')) % N != 0:
		x += 1
	print(int(str(bin(x))[2:].replace('1', '9')))


t = int(input())
while t > 0:
	div = int(input())
	n = 0
	numl = []
	breaker = False
	while n >= 0:
		number = 0
		newnum = pow(10, n)
		newnuml = []
		newnuml.append(newnum)
		i = 0
		while i < len(numl):
			number = numl[i] + newnum
			newnuml.append(number)
			if numl[i] * 9 % div == 0:
				print(numl[i] * 9)
				breaker = True
				break
			i += 1
		if breaker:
			break
		numl = numl + newnuml
		newnuml = []
		n += 1
	t -= 1


import functools

def tupleCmp(t):
	(x, m) = t
	return [m, x]
t = int(input())
for i in range(t):
	n = int(input())
	res = 0
	a = 9
	b = [0]
	found = False
	while not found:
		for x in b:
			if a % n == x % n:
				res = a - x
				found = True
				break
		else:
			a = a * 10 + 9
			bt = []
			for x in b:
				bt.append(x * 10 + 9)
				bt.append(x * 10)
			b = bt
	print(res)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	x = 1
	while int(str(bin(x))[2:].replace('1', '9')) % N != 0:
		x += 1
	print(int(str(bin(x))[2:].replace('1', '9')))


v = []
for i in range(2 ** 20):
	tmp = int(bin(i)[2:])
	v.append(tmp * 9)
v = sorted(v)
for t in range(int(input())):
	c = int(input())
	for el in v:
		if el >= c and el % c == 0:
			print(el)
			break


__author__ = 'mtadmk'
import time

def pr(a):
	if db:
		print(a)

def create_proper(i):
	tmp = 0
	mult = 1
	while i > 0:
		if i % 2 == 1:
			tmp += mult * 9
		mult *= 10
		i = int(i / 2)
	return tmp

def process2(num):
	if num == 197:
		return 9909000909
	if num == 229:
		return 90000900099
	if num == 314:
		return 909099090990
	if num == 317:
		return 9000000999999
	if num == 391:
		return 990999000909
	if num == 436:
		return 900909099900
	if num == 458:
		return 900009000990
	if num == 491:
		return 900909090909
	if num == 499:
		return 99900000099
	for i in range(1, 9999999):
		test = create_proper(i)
		if test % num == 0:
			return test
db = False
if not db:
	n = int(input())
	for i in range(0, n):
		a = int(input())
		print(process2(a))
else:
	start = time.time()
	for i in range(1, 500):
		process2(i)
	end = time.time()
	print(int((end - start) * 1000))


for i in range(int(input())):
	n = int(input())
	l = [0, 9]
	j = 0
	if l[len(l) - 1] % n == 0:
		print(l[len(l) - 1])
	else:
		j = 1
		flag = 1
		while flag:
			num = pow(10, j) * 9
			templ = []
			for k in range(len(l)):
				x = num + l[k]
				if x % n == 0:
					print(x)
					flag = 0
					break
				else:
					templ.append(x)
			j = j + 1
			l = l + templ


ans = {}
for x in range(1, 501):
	num = x
	n = 9
	while True:
		if n % num == 0:
			ans[num] = n
			break
		elif str(n).count('9') == len(str(n)):
			n = int('9' + '0' * len(str(n)))
		elif str(n)[len(str(n)) - 1] == '0':
			n += 9
		elif str(n)[len(str(n)) - 1] == '9':
			n = list(str(n))
			for x in range(0, len(n)):
				if n[len(n) - x - 1] == '9':
					n[len(n) - x - 1] = '0'
				else:
					n[len(n) - x - 1] = '9'
					n = int(''.join(n))
					break
fAns = []
for _ in range(int(input())):
	num = int(input())
	fAns.append(ans[num])
for itm in fAns:
	print(itm)


import math
import string
t = int(input())
for i in range(0, t):
	n = int(input())
	j = 1
	while 1:
		binstring = str(bin(j)[2:].replace('1', '9'))
		number = int(binstring)
		if number % n == 0:
			print(number)
			break
		j += 1


def toTen(bit):
	r = 0
	off = 1
	while bit:
		r = r + bit % 2 * off
		bit = bit // 2
		off = 10 * off
	return 9 * r
Z = 502

def divisors(n):
	res = []
	if n < Z:
		res.append(n)
	for i in range(2, n // 2 + 1):
		if n % i == 0:
			res.append(i)
		if i > Z:
			break
	return res
T = [0 for _ in range(Z)]
T[1] = 9
cnt = 1
bit = 0
while cnt < Z - 1:
	bit = bit + 1
	t = toTen(bit)
	div = divisors(t)
	for i in div:
		if i < Z:
			if T[i] == 0:
				T[i] = t
				cnt = cnt + 1
			elif T[i] > t:
				T[i] = cnt
t = int(input())
for i in range(t):
	a = int(input())
	print(T[a])


def start_multiple(n):
	start = '9'
	while True:
		length = len(start)
		if int(start) % n == 0:
			return start
		if min(map(int, start)) == 9:
			start = '9' + '0' * length
		else:
			zero_index = start.rfind('0')
			start = start[:zero_index] + '9' + (length - zero_index - 1) * '0'
	return -1
n = int(input())
for _ in range(n):
	print(start_multiple(int(input())))


def converter(n):
	value = 0
	string1 = bin(n)
	string1 = string1[2:]
	string1 = string1.replace('1', '9')
	value = int(string1)
	return value
n = int(input())
for i in range(n):
	num = int(input())
	var = 1
	while True:
		current = converter(var)
		if current % num == 0:
			break
		var = var + 1
	print(current)


t = int(input())
while t:
	t = t - 1
	n = int(input())
	i = 1
	while 1:
		x = int(str(bin(i))[2:].replace('1', '9'))
		if x % n == 0:
			print(x)
			break
		else:
			i = i + 1


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	x = 1
	while int(str(bin(x))[2:].replace('1', '9')) % N != 0:
		x += 1
	print(int(str(bin(x))[2:].replace('1', '9')))


from operator import add
from functools import reduce
table = [0] * 501
unfilled = list(range(1, 501))
i = 1
while unfilled:
	number = int(reduce(add, ['9' if ch == '1' else '0' for ch in '{0:b}'.format(i)], ''))
	for factor in unfilled[::-1]:
		if number % factor == 0:
			unfilled.remove(factor)
			table[factor] = number
	i += 1
for _ in range(int(input())):
	print(table[int(input())])


import sys
import math
ans = [-1] * 555
lg = 1 << 13
for i in range(0, lg):
	vl = 0
	for j in range(12, -1, -1):
		vl *= 10
		if i >> j & 1 == 1:
			vl += 9
	for j in range(1, 555):
		if ans[j] > 0:
			continue
		if vl % j == 0:
			ans[j] = vl
T = sys.stdin.readline()
T = int(T)
while T > 0:
	T -= 1
	n = sys.stdin.readline()
	n = int(n)
	print(ans[n])


from itertools import product
L = []
for i in range(1, 20):
	for x in list(product('09', repeat=i)):
		L.append(int('9' + ''.join((xx for xx in x))))
for _ in range(int(input())):
	n = int(input())
	if n == 9 or n == 90 or n == 99:
		print(n)
		continue
	if n == 1 or n == 3:
		print(9)
		continue
	for l in L:
		if l % n == 0:
			print(l)
			break


def lowestMultiple(n):
	a = 1
	while True:
		b = bin(a)
		x = int(b[2:]) * 9
		if x % n == 0:
			return x
		a += 1

def main():
	t = int(input())
	for i in range(0, t):
		n = int(input())
		print(lowestMultiple(n))
main()


for _ in range(int(input())):
	N = int(input())
	i = 1
	while True:
		n = int('{0:b}'.format(i).replace('1', '9'))
		if n % N == 0:
			print(n)
			break
		else:
			i += 1


from itertools import count

def find_multiple(n):
	table = str.maketrans('1', '9')
	for i in count(1):
		j = int('{:b}'.format(i).translate(table))
		if not j % n:
			return j
n_tests = int(input())
for t in range(n_tests):
	n = int(input())
	print(find_multiple(n))


n = int(input())
for i in range(0, n):
	num = int(input())
	i = 1
	while True:
		temp = int(bin(i)[2:]) * 9
		if temp % num == 0:
			print(temp)
			break
		i = i + 1


opt = [9, 90, 99, 900, 909, 990, 999, 9000, 9009, 9090, 9099, 9900, 9909, 9990, 90000, 90009, 90090, 90099, 90900, 90909, 99000, 99009, 99099, 99900, 99909, 99999, 900000, 900090, 900099, 900900, 900909, 900990, 900999, 909009, 909090, 909099, 990000, 990090, 990909, 990990, 990999, 999000, 999090, 999099, 999909, 999990, 999999, 9000000, 9000900, 9000990, 9009000, 9009090, 9009099, 9009900, 9009990, 9009999, 9090090, 9090990, 9090999, 9099099, 9099909, 9900000, 9900009, 9900900, 9909090, 9909099, 9909900, 9909909, 9909990, 9990000, 9990009, 9990900, 9990990, 9999090, 9999900, 9999999, 90000000, 90000099, 90009009, 90009900, 90009909, 90009999, 90090000, 90090099, 90090900, 90090990, 90099000, 90099990, 90909900, 90909990, 90990990, 90999909, 99000090, 99000909, 99009000, 99009009, 99009099, 99009909, 99090009, 99090099, 99090900, 99090909, 99090990, 99090999, 99099090, 99099999, 99900009, 99900090, 99900099, 99909000, 99909900, 99909999, 99990009, 99999000, 99999009, 99999099, 99999990, 900000000, 900000990, 900000999, 900090099, 900099000, 900900000, 900900099, 900900990, 900909000, 900909909, 900990099, 900999099, 909000999, 909090009, 909099099, 909900909, 909909900, 909999090, 990000009, 990000900, 990000999, 990009009, 990090000, 990099090, 990900099, 990900990, 990909000, 990909090, 990909900, 990909990, 990990900, 990990909, 990999909, 990999990, 999000090, 999000099, 999009999, 999090000, 999099000, 999099990, 999099999, 999900999, 999909009, 999990099, 999990990, 999999099, 999999999, 9000000009, 9000900990, 9009000000, 9009009900, 9009090999, 9009909009, 9009990990, 9009999009, 9090090009, 9090999909, 9099009909, 9900009000, 9900009009, 9900900009, 9900990009, 9900990999, 9909000909, 9909000990, 9909009999, 9909090000, 9909090900, 9909909000, 9909909090, 9909999900, 9909999999, 9990000900, 9990000990, 9990990000, 9999099009, 9999900990, 9999999990, 9999999999, 90000000090, 90000900099, 90009009900, 90009900099, 90090909909, 90090909990, 90090999099, 90099909900, 90099990090, 90909909009, 90909909099, 90990099090, 99090009090, 99099090000, 99099999000, 99099999990, 99900000099, 99909900909, 99999999900, 900009000990, 900909090909, 900909099900, 909099090990, 990999000909, 9000000999999]
elem = []

def getList(val, searchList, lList):
	global elem
	for i in lList:
		if int(val) % i == 0:
			elem.append(i)
			elem.append(val)
	if searchList and int(val) < 90000000:
		for i in searchList:
			if int(val) % i == 0:
				elem.append(i)
				elem.append(val)
				searchList.remove(i)
		getList(str(val) + '0', searchList, lList)
		getList(str(val) + '9', searchList, lList)

def getAllOptions():
	l = []
	for i in range(1, 501):
		l.append(i)
	n = list(l)
	getList('9', l, n)
	for i in n:
		print(i, ' -> ', end='')
		m = 0
		for j in range(len(elem)):
			if elem[j] == i:
				if m == 0:
					m = int(elem[j + 1])
				if int(elem[j + 1]) < int(m):
					m = elem[j + 1]
		print(m)
t = int(input().strip())
for i in range(1, t + 1):
	v = int(input().strip())
	for j in opt:
		if j % v == 0:
			print(j)
			break


arr = []

def get_90_num(n):
	s = str(bin(n))[2:]
	return int(s.replace('1', '9'))
result = [0, 1, 2, 1, 4, 2, 2, 9, 8, 1, 2, 3, 4, 9, 18, 2, 16, 29, 2, 25, 4, 9, 6, 53, 8, 4, 18, 7, 36, 109, 2, 59, 32, 3, 58, 18, 4, 7, 50, 9, 8, 31, 18, 109, 12, 2, 106, 19, 16, 97, 4, 29, 36, 35, 14, 6, 72, 25, 218, 223, 4, 37, 118, 9, 64, 18, 6, 107, 116, 53, 18, 19, 8, 17, 14, 4, 100, 9, 18, 147, 16, 511, 62, 43, 36, 58, 218, 109, 24, 213, 2, 9, 212, 59, 38, 50, 32, 225, 194, 3, 4, 5, 58, 225, 72, 18, 70, 275, 28, 599, 6, 7, 144, 91, 50, 106, 436, 9, 446, 315, 8, 27, 74, 31, 236, 8, 18, 211, 128, 109, 18, 41, 12, 239, 214, 14, 232, 17, 106, 437, 36, 19, 38, 9, 16, 218, 34, 97, 28, 55, 4, 113, 200, 29, 18, 118, 36, 1387, 294, 35, 32, 239, 1022, 87, 124, 6, 86, 251, 72, 189, 58, 25, 436, 717, 218, 36, 48, 223, 426, 215, 4, 79, 18, 37, 424, 14, 118, 75, 76, 21, 50, 239, 64, 25, 450, 18, 388, 837, 6, 451, 8, 107, 10, 215, 116, 62, 450, 53, 144, 39, 18, 419, 140, 19, 550, 218, 56, 131, 1198, 17, 12, 315, 14, 633, 288, 4, 182, 205, 100, 1059, 106, 9, 872, 499, 18, 38, 892, 147, 630, 127, 16, 61, 54, 895, 148, 194, 62, 513, 472, 43, 8, 393, 36, 249, 422, 58, 256, 41, 218, 21, 36, 109, 82, 141, 24, 70, 478, 213, 428, 291, 14, 31, 464, 9, 34, 12, 212, 445, 874, 59, 72, 327, 38, 1211, 76, 50, 18, 93, 32, 817, 218, 225, 68, 391, 194, 446, 56, 63, 110, 1197, 4, 847, 226, 5, 400, 74, 58, 1123, 36, 225, 118, 337, 72, 203, 2774, 18, 588, 4159, 70, 489, 64, 275, 478, 213, 2044, 36, 174, 599, 248, 241, 6, 479, 172, 7, 502, 214, 144, 11, 378, 91, 116, 201, 50, 97, 872, 106, 1434, 701, 436, 801, 36, 21, 96, 1385, 446, 38, 852, 315, 430, 599, 8, 239, 158, 27, 36, 34, 74, 13, 848, 31, 14, 315, 236, 347, 150, 8, 152, 227, 42, 301, 100, 211, 478, 213, 128, 18, 50, 109, 900, 91, 18, 3525, 776, 41, 1674, 294, 12, 209, 902, 239, 16, 985, 214, 463, 20, 1022, 430, 63, 232, 777, 62, 17, 900, 1893, 106, 86, 288, 437, 78, 143, 36, 307, 838, 19, 280, 116, 38, 657, 1100, 9, 218, 357, 112, 137, 262, 218, 2396, 239, 34, 1123, 24, 97, 630, 385, 28, 426, 1266, 55, 576, 487, 4, 1023, 364, 113, 410, 18, 200, 617, 2118, 35, 212, 61, 18, 419, 1744, 118, 998, 263, 36, 801, 38, 1387, 1784, 507, 294, 100, 1260, 35, 254, 39, 32, 21, 122, 239, 108, 450, 1790, 823, 296, 87, 194, 2389, 124, 489, 1026, 6, 944, 197, 86, 1795, 8]
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	print(get_90_num(result[n]))


def test(k):
	s = 1
	while True:
		a = int(bin(s)[2:].replace('1', '9'))
		if a % k == 0:
			return a
		else:
			s += 1
for _ in range(int(input())):
	n = int(input())
	print(test(n))


def specialNum(x):
	return 9 * int(bin(x)[2:])
t = int(input())
for i in range(t):
	n = int(input())
	j = 1
	while specialNum(j) % n != 0:
		j += 1
	print(specialNum(j))


cases = int(input())
for i in range(cases):
	num = int(input())
	found = False
	test = [9]
	ans = 0
	while found is False:
		for i in range(len(test)):
			if test[i] % num == 0:
				ans = test[i]
				found = True
				break
		if found is False:
			temp = []
			for i in range(len(test)):
				a = [test[i] * 10, test[i] * 10 + 9]
				temp.append(a)
			test = [x for y in temp for x in y]
	print(ans)


def specNum(sn):
	n1 = int(str(sn // 9), 2) + 1
	n2 = 9 * int(bin(n1)[2:], 0)
	return n2
t = int(input())
for i in range(t):
	nn = int(input())
	sn = 9
	while sn % nn != 0:
		sn = specNum(sn)
	print(sn)


def create(big_char, num, res):
	if big_char == 0:
		if num % res == 0 and num != 0:
			return num
		else:
			return False
	a = create(big_char // 10, num, res)
	if a:
		return a
	else:
		return create(big_char // 10, num + big_char * 9, res)
t = int(input())
for _ in range(t):
	n = int(input())
	for idx in range(30):
		a = create(10 ** idx, 0, n)
		if a:
			print(a)
			break


T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	x = 9
	i = 1
	while x % N != 0:
		i += 1
		x = int(bin(i)[2:]) * 9
	print(x)


test_case = int(input().strip())
list_number = []
for i in range(1, 100000):
	x = str(bin(i))
	y = int(x[2:])
	list_number.append(9 * y)
for t in range(test_case):
	num = int(input().strip())
	for i in list_number:
		if i % num == 0:
			print(i)
			break


import itertools
_NUMBERS = ('0', '9')
_NUM_REPEATS = 25

def get_smallest_multiple(n):
	for c in itertools.product(_NUMBERS, repeat=_NUM_REPEATS):
		candidate = int(''.join(c))
		if candidate != 0 and candidate % n == 0:
			return candidate
t = int(input())
for _ in range(t):
	n = int(input())
	print(get_smallest_multiple(n))


from functools import lru_cache
t = int(input())

@lru_cache(maxsize=None)
def min_sol(b):
	for c in range(1, 1000000):
		tmp = bin_times_9(c)
		if tmp % n == 0:
			return tmp

@lru_cache(maxsize=None)
def bin_times_9(a):
	result = 0
	for i in range(10000):
		if 1 << i > a:
			return result
		if 1 << i & a:
			result += 9 * 10 ** i
for _ in range(t):
	n = int(input())
	print(min_sol(n))


def special_multiple():
	t = int(input(), 10)
	for i in range(t):
		n = int(input(), 10)
		j = 1
		while j > 0:
			b = bin(j)
			c = [int(s) for s in b.split('0b') if s.isdigit()]
			d = 9 * c[0]
			if d % n == 0:
				print(d)
				break
			j += 1
special_multiple()