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

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

hide comments
2017-01-24 07:16:49
Easy one))
2017-01-02 19:32:58
My 50th :)
2016-09-06 15:05:43 hacker
tle in python bruteforce why?

Last edit: 2016-09-06 15:05:58
2016-06-18 23:04:51
brute force .... :-) AC!
2016-06-14 19:01:46
Easy! :D
2015-08-19 11:57:10 SangKuan
brute-force enough,but not a good way
2015-08-01 22:42:52 vedang
@sesh
We have to find the smallest number greater than or equal to n which is divisible by its own sum of digits, not the sum of digits of n. I got many WAs due to this!

Last edit: 2015-08-01 22:43:29
2015-06-13 00:17:44 Piyush Kumar
Simple brute-force. Should be moved to tutorial.
2015-06-12 07:47:43 Harshit
EASY.......
2015-05-30 15:55:22 Bhuvnesh Jain
AC ;) read question carefully.. easy though

Last edit: 2015-06-05 00:29:53
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.