# Divisible by 3

Easy

Execution time limit is 1 second

Runtime memory usage limit is 64 megabytes

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.

## Examples

Input #1

Answer #1

Input #2

Answer #2

Submissions 1K

Acceptance rate 17%