Smallest Integer with a Given Digit Sum

You are given a positive integer n. Your task is to find the smallest positive integer X such that the sum of its digits equals n. In other words, if S(X) denotes the sum of the digits of X, find the minimum X satisfying

$$S(X)=n.$$

Hint: If n ≤ 9, then the answer is simply n. Otherwise, if you let

$$q = \left\lfloor \frac{n}{9} \right\rfloor, \quad r = n \mod 9, $$

one valid construction for X is to write down q copies of digit 9 and the digit r, and then arrange them so that the smallest non-zero digit is at the beginning. More formally, one correct answer is given by:

$$X = \overline{(r)\,9\,9\,\ldots\,9},$$

with the special note that when r = 0 (i.e. when n is a multiple of 9), X is simply the integer consisting of q copies of 9.

inputFormat

The first line of input contains a single integer T representing the number of test cases. Each of the following T lines contains a single integer n (1 ≤ n ≤ 10⁵ or as specified) for which you should compute the answer.

outputFormat

For each test case, output the smallest integer X (in its usual decimal representation with no leading zeros) such that the sum of its digits is equal to n. Each answer should be printed on a new line.

## sample

3
1
10
18

1
19
99

</p>