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 \(N\), 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\).

Input

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

Output

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

Example

234234234

834834834

8118

8118

Ràng buộc

• Có 20% số test ứng với 20% số điểm thỏa mãn: \(1 \leq N \leq 99\).
• Có 40% số test ứng với 40% số điểm thỏa mãn: \(100 \leq N \leq 10^{16}\).
• Có 40% số test còn lại ứng với 40% số điểm không có giới hạn gì thêm.