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?
X is made up of one or more occurences of 9 and zero or more occurences of 0.
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.
Print the answer X to STDOUT corresponding to each test case. The output should not contain any leading zeroes.
1 <= T <= 104
1 <= N <= 500
3 5 7 1
90 9009 9
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
Solution in Python
from itertools import product def special(n): i = 0 while True: for j in product(*[[0,9]]*i) or : s = "9"+"".join(map(str,j)) if not int(s)%n: return s i+=1 for _ in range(int(input())): n = int(input()) print(special(n))