For a given integer $$n$$, find the smallest integer that is divisible by $$n$$ and from which the sum of the digits equals $$n$$.

Input

The input consists of $$t$$ test cases ($$t \leq 50$$). The first line of the input contains an integer $$t$$, followed by  $$t$$ lines that describe the various test cases. Every case is described as an integer $$n$$ ($$0 < n \leq 100$$).

Output

Write out the natural number asked for each test case, without leading zeros.

Example

Input:

2
1
10

Output:

1
190