Smallest Integer With Given Digit Sum

Given a non-negative integer \(S\), find the smallest integer \(x\) such that the sum of the digits of \(x\) equals \(S\). When \(S = 0\), the answer is defined to be 0. Otherwise, one should construct \(x\) by greedily choosing digits (at most 9 each) and concatenating them in a way that produces the minimum possible integer.

For example, if \(S = 10\), then the answer is 19 since \(1+9=10\) and 19 is the smallest number whose digits sum to 10. This problem tests basic greedy and constructive strategies to form minimal numbers with a given property.

inputFormat

The first line of input contains an integer \(T\), representing the number of test cases. Each of the following \(T\) lines contains one integer \(S\): the desired sum of digits.

outputFormat

For every test case, output on a new line the smallest integer whose digits sum to \(S\).

3
1
10
18

1
19
99