eolymp
bolt
Try our new interface for solving problems
Problems

Divisible by 3

Divisible by 3

The number is given. Stepan wants to replace one digit so that the new number will be divisible by 3 and will be as maximal as possible. You must necessarily replace one digit, even if the number is already divisible by 3. As Stepan only started to attend the programming courses, he asks you to help.

Input

One positive integer is given. Its length is no more than 100 digits.

Output

Print one positive integer satisfying the following conditions:

  • it must be different from the given number only in one digit.
  • it must be divisible by 3.
  • it must be as maximal as possible among all such numbers.
Time limit 1 second
Memory limit 64 MiB
Input example #1
123
Output example #1
723
Input example #2
8
Output example #2
9
Source 2016 ACM Ukraine, First Stage, April 16