SPCQ - Gopu and Digits Divisibility


One day Little Gopu was playing with numbers. As he is little boy, he was wondering about divisibility rules that how they apply and what is the logic behind them. Few days ago he has also learnt how to find sum of digits of a number. 

He thought about finding the smallest number greater than or equal to n, which is a "nice" number. A number is called "nice" if it is divisible by sum of its digits. He is unable to solve this puzzle. Can you write a program to help the Little Gopu?

eg. if n = 11, 11 is not divisible by 1 + 1 = 2, But 12 is divisible by 1 + 2 = 3. So answer for case n = 11 should be 12.

Input

First line contains T : number of test cases. (1 <= T <= 10^4).

For each test case, It contains a single integer n in a line, (1 <= n <= 10^18).

Output

For each test case, output the smallest "nice" number greater or equal to n.

Example

Input:
3
11
22
2 Output: 12
24

hide comments
Seshadri R: 2015-04-08 10:55:49

@Lakshman: Can you please check your input and output samples? 4578678567857 sums up to 83 and your quoted output 4578678567876 is not evenly divisible by 83. Again, your second input 6709978986847584 results in 105, but the quoted output 6709978986847640 does not divide 105.

varun yadav: 2015-04-06 20:28:31

my program is showing runtime error on ideone as well as if i use it on my compiler it shows correct answer for input under the range of long long int but shows rong answer for large inputs(which are out of range of long long int),,,,, my code is http://ideone.com/********* ................. plzzz help :(

Last edit: 2015-04-07 00:49:31
darol: 2015-01-22 08:15:43

ok thx [Lakshman] found the problem, forget to change sum field after increasing number by 1 so it wass comparing always to original number digit sum :)

[Lakshman]: 2015-01-22 04:11:06

@Dariusz Lelek I checked with some randon cases and for maximum your code is giving wrong answer. Check with this input
2
4578678567857
6709978986847584
output
4578678567876
6709978986847640

darol: 2015-01-22 03:25:37

Hmm i keep getting WA not sure whats wrong, set the limits for n. Checked few outputs with calc - seems giving correct answers. If you could tell me what am i doing wrong i would be greatful! :)
Heres my coding in Java: <snip>

Last edit: 2023-08-06 11:19:38
Dushyant Singh: 2015-01-21 20:58:44

AC! :-)


Added by:praveen123
Date:2013-12-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge