The Owl and the Fox

Interview

Time limit1sMemory limit256 MB

Summary

Given N, find the largest integer below N whose digit sum is exactly one less than the digit sum of N.

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

Problem

Fox Mithra has finally learned the numbers. He knows one, two, three, and also zero, minus one, minus two, and so on. He opened his textbook and copied the integers onto the wall of his zoo enclosure one by one, from the smallest to the biggest.

An owl landed on the branch above Mithra's head and said, "Something is wrong with the sequence on your wall. You should put 30 between 20 and 22."

"Why?"

"Because the importance of a number is judged by the sum of its digits. So 30 is less important than 22 and more important than 20. And 30 should sit at the same distance from 20 and from 22, because its digit sum differs by exactly one from both of them."

"You are clever," replied Mithra. "Can you help me put the sequence right? Each time I tell you a number $N$ , tell me the closest smaller number whose digit sum is one less than the digit sum of $N$ ."

"With pleasure," the owl nodded.

Do the owl's job. Given an integer $N$ , find the largest integer smaller than $N$ whose digit sum is exactly one less than the digit sum of $N$ .

Input

The input holds several test cases. Each case is one line with a single integer $N$ ( $1 \le N \le 100000$ ). The last line contains the string END and no other symbols, and the input ends there.

Output

For each test case print the number the fox asked for on its own line. An answer always exists for every $N$ in the given range.

Examples4

Example 1
Input
```
30
199
1000
1520
END
```
Expected output
```
20
198
0
1510
```
Example 2
Input
```
1
END
```
Expected output
```
0
```
Example 3
Input
```
100000
END
```
Expected output
```
0
```
Example 4
Input
```
2
3
9
10
11
END
```
Expected output
```
1
2
8
0
10
```