INUMBER - Interesting number

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

Added by:Roman Sol
Date:2005-01-13
Time limit:7s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:XII team championship of St.-Petersburg in programming

hide comments
2009-07-12 10:43:54 Ruslan
how mach the answer can be?
for example for 1000 answer must be at least 112 dig number am i right??
Re : surely, at least 1000/9 + 1 digits

Last edit: 2009-07-19 20:50:31
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.