PROG0004 - Interesting numbers

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

Voor een gegeven natuurlijk getal $n$, vind het kleinste natuurlijk getal dat deelbaar is door $n$ en waarvan de som van de cijfers gelijk is aan $n$.

Invoer

De invoer bestaan uit $t$ testgevallen ($t \leq 50$). De eerste regel van de invoer bevat een natuurlijk getal $t$. Daarna volgen $t$ regels die de verschillende testgevallen omschrijven. Elk geval wordt omschreven door een natuurlijke getal $n$ ($0 < n \leq 100$).

Uitvoer

Schrijf voor elk testgeval het gevraagde natuurlijk getal uit op een afzonderlijke regel, zonder voorloopnullen.

Voorbeeld

Invoer:

2
1
10

Uitvoer:

1
190

Added by:Peter Dawyndt
Date:2011-07-09
Time limit:30s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.