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
zarif_2002: 2019-02-19 12:09:44

after 1 hours, AC in one go.

darkknight21: 2018-09-01 00:50:38

Really good one
iterative DP + BFS + backtracking for printing the solution

sukhbir947: 2017-12-19 23:31:49

Challenging one...!!
Important Lesson learnt: For solving bfs, using "array" instead of "map" for storing visit state reduces complexity by large fraction.

Sarthak Munshi: 2016-09-05 22:15:57

Using STL gives WA while simulating using an array gives AC . Weird . Spent 2 full days on getting this passed .

kartikay singh: 2016-06-21 21:24:01

dp + bfs + backtracking = AC :-B

singhmanmeet40: 2016-06-21 02:21:06

if using bfs don't use string to store no from starting
use backtracking ie maintain the parent's address in some form and calculate the number in the end

Navneet Kumar Srivastava: 2016-04-08 07:10:46

Can someone explain why the output is 1 when input is 1?

shubham_goyal: 2016-01-21 01:26:46

19 sums up to 10, but it is not divisible by 10. thats y.

kejriwal: 2016-01-16 10:46:46

why is the answer of 2nd case 190.. ? 19 also sums upto 10 !! ?

Rohit Agarwal: 2015-09-07 22:06:56

Very challenging problem. Was fun to implement it. The hardest part was to print the number. Finally AC ;) :D
STL and w/o STL both. :)


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