Кратное трём

Дано число. Степан хочет заменить в нем одну цифру таким образом, чтобы новое число делилось на 3 и было максимально возможным. В заданном числе нужно обязательно заменить одну цифру, даже если оно уже делится на 3. Поскольку Степан только начал посещать факультатив по программированию, то он просит помощи у Вас.

Входные данные

Дано одно натуральное число. Длина числа может достигать 100 цифр.

Выходные данные

Выведите натуральное число, удовлетворяющее следующим условиям:

• Новое число должно отличаться от заданного ровно одной цифрой.

• Новое число должно делиться на 3.

• Новое число должно быть максимально возможным среди всех таких чисел.

Примеры