Harshad Numbers

Interview

Time limit2sMemory limit512 MB

Summary

Find the smallest number at least n that is divisible by its digit sum, for n up to 1,000,000,000.

Level: Easy3 of 10
Topics: Math, Brute force
Solved: No attempts yet

Problem

We're all familiar with harshad numbers. For this problem, you will ... what's that? You aren't familiar with harshad numbers? They're also known as Niven numbers. Does that ring a bell? Anything???

Well, it's a simple enough concept. A harshad number is a number which is evenly divisible by the sum of its digits. For example, 24 is a harshad number: the sum of its digits is 2 + 4 = 6 and 24 is divisible by 6. 156 is also a harshad number, since 1 + 5 + 6 = 12 and 156 = (12)(13). 157 is NOT a harshad number since it is not divisible by 1 + 5 + 7 = 13.

OK, let's start over.

We're all familiar with harshad numbers. For this problem, you will be given a number n and must find the smallest harshad number ≥ n.

Input

Input consists of a single line containing a positive integer n ≤ 1 000 000 000.

Output

Display the smallest harshad number greater than or equal to n.

Examples3

Example 1
Input
```
24
```
Expected output
```
24
```
Example 2
Input
```
25
```
Expected output
```
27
```
Example 3
Input
```
987654321
```
Expected output
```
987654330
```