RoAlgo Contest #7 | nr9

"How many problems do we need for this contest?"

Task

Given a natural number $n$, you need to determine the largest natural number less than or equal to $n$, such that no matter how you rearrange its digits, it is not divisible by $9$.

Input data

The first line will contain the number $n$.

Output data

The first line will contain the required number.

Constraints and clarifications

• $10 \leq n \leq 10 ^ 9$

Example 1

stdin

69

stdout

69

Example 2

stdin

99

stdout

98

Explanation

In the first example, $69$ itself is not divisible by $9$, and any rearrangement of its digits (i.e., $96$) is also not divisible by $9$. Thus, $69$ is the largest number that meets the condition.

In the second example, $99$ is divisible by $9$. Therefore, we need to find the next largest number less than $99$ that is not divisible by $9$ in any rearrangement of its digits, which is $98$.