nr9

Time limit: 0.05s Memory limit: 64MB Input: Output:

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

Task

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

Input data

The first line will contain the number nn.

Output data

The first line will contain the required number.

Constraints and clarifications

  • 10n10910 \leq n \leq 10 ^ 9

Example 1

stdin

69

stdout

69

Example 2

stdin

99

stdout

98

Explanation

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

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

Log in or sign up to be able to send submissions!