For the given number n find the minimal positive integer divisible 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