Carl is fascinated with numbers, especially the GCD (greatest common divisor) function. What he likes to do is that he takes a number X and he computes the sum of its digits S(X). Then, he calculates the GCD of X and S(X). He wants to find values of X such that GCD(X, S(X)) > 1.
Given an integer N, help him find the least number X >= N that satisfies this property.
Explanation for the first sample test case:
Let X = 11. The sum of the digits of X is 1+1=2. The GCD of 11 and 2 is , so this does not satisfy the property.
Let X = 12. The sum of the digits of X is 1+2=3. The GCD of 12 and 3 is , so this satisfies the property.
Since is the least number >= 11 that satisfies the property, it is the answer for the first sample test.
Input Format
The first line of the input contains the number of test cases .
The following lines each contain a single number ().
Sample Input
3
11
31
75
Output Format
Output lines, where the ith line contains a single number, , that is the answer to the ith test case.
Sample Output
12
33
75You must be logged in to submit a solution.