Hackerrank - Special Multiple Solution

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⁴
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

Solution in Python

from itertools import product
def special(n):
    i = 0
    while True:
        for j in product(*[[0,9]]*i) or [9]:
            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))