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

hide comments
VISHAL DEEPAK AWATHARE: 2015-02-19 08:49:57

once you find a way to generate the results we can well do /

Last edit: 2015-02-19 08:51:11
Archit Jain: 2014-07-18 13:09:56

enjoyed solving this

IKKA: 2014-04-21 16:35:22

how to get accepted using STL

yousef hadder: 2014-03-31 17:19:23

got AC But with 6.50S,, any suggestions for a faster algorithm ??

Kamil: 2014-01-05 19:07:12

What kind of trick do we need to pass memory limit?

Shafaet: 2012-12-27 09:00:32

@kshitij agrawal: I've used STL and got ac.

kshitij agrawal: 2011-12-19 11:42:43

Difficult one ..... Don't use STL...

P.S: I am 279th user to do this 279th problem .. :)

Last edit: 2011-12-19 12:25:55
Hy Trường Sơn: 2010-10-20 14:35:11

i think so

Last edit: 2010-10-20 14:35:45
.:: Pratik ::.: 2009-07-31 08:40:40

You don't need big int...

Drew Saltarelli: 2009-07-12 21:00:43

input : 1000
output : 1999999999999999999999999999999999999999999999999
999999999999999999999999999999999999999999999999999999999999
999000

which is a 118 digit number. You will need bignums or a
language that can support arbitrary big numbers (i.e. python)

Last edit: 2009-07-12 22:09:21

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