For the given number n find the minimal positive integer divisable by n, with the sum of digits equal to n.

Input

t – the number of test cases, then t test cases follow. (t <= 50)
Test case description:
n - integer such that 0 < n <= 1000

Output

For each test case output the required number (without leading zeros).

Example

Input:
2
1
10
Output:
1
190