Cho số tự nhiên ~N~ (có không quá ~100~ chữ số). Hãy thay đúng một loại chữ số trong ~N~ (từ ~0~ đến ~9~) thành một loại chữ số khác (cũng từ ~0~ đến ~9~ ) sao cho số cuối cùng nhận được không có chữ số ~0~ ở đầu và là số lớn nhất chia hết cho ~9~.

Yêu cầu: Tìm số lớn nhất có thể thu được sau khi thay đúng một loại chữ số trong , sao cho số đó chia hết cho ~9~. Nếu không có cách nào thỏa mãn điều kiện, in ra 0.

Dữ liệu nhập vào từ bàn phím

• Một dòng chứa duy nhất số tự nhiên ~N~ ~(1 \le N \le 10^{100})~.

Kết quả ghi ra màn hình

• Một số tự nhiên duy nhất là kết quả của bài toán.

Chấm điểm

• Có 20% số test ứng với 20% số điểm của bài thoả mãn: ~1 \le N \le 99~;
• 40% số test khác ứng với 40% số điểm của bài thoả mãn: ~100 \le N \le 10^{16}~;
• 40% số test còn lại ứng với 40% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Dữ liệu 1

234234234

Kết quả 1

834834834

Giải thích

• Đổi tất cả chữ số ~2~ thành chữ số ~8~ để được số lớn nhất chia hết cho ~9~.

Dữ liệu 2

8118

Kết quả 2

8118

Giải thích

• Không có cách thay đổi nào tốt hơn, giữ nguyên là tốt nhất.