Trong buổi ngoại khoá, An tình cờ tìm thấy một cuốn sách cũ nằm khuất trong góc thư viện trường. Trên trang bìa có ghi một xâu ký tự lạ \(S\) (chỉ gồm chữ cái Latin in thường). An phát hiện rằng nếu cậu chọn một số ký tự từ xâu này và giữ nguyên thứ tự của chúng thì có thể tạo thành xâu đọc xuôi cũng giống đọc ngược - một xâu đối xứng rất đẹp mắt. An muốn tìm xâu đối xứng dài nhất mà cậu có thể tạo ra từ \(S\) để giải mã bí ẩn trang bìa.

Hãy giúp An tìm độ dài xâu đối xứng dài nhất tạo được theo cách này.

Định dạng đầu vào

• Một dòng duy nhất chứa xâu \(S\) (độ dài \(|S| \le 5000\)), chỉ gồm chữ cái Latin in thường.

Định dạng đầu ra

• In ra độ dài xâu đối xứng dài nhất có thể tạo được.

Ví dụ

Input:

bbabcbcab

Output:

7

Ràng buộc

• \(30\%\) số điểm ứng với \(|S| \le 100\).
• \(30\%\) số điểm ứng với \(|S| \le 1000\).
• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.