Tèo nhận được một bài tập về nhà từ thầy Hùng. Thầy cho một xâu ký tự \(S\) (chỉ gồm chữ cái Latin in thường) và yêu cầu Tèo cắt xâu này thành các đoạn liên tiếp sao cho mỗi đoạn đều là một xâu đối xứng (đọc xuôi hay đọc ngược đều giống nhau). Tèo muốn số vết cắt là ít nhất, tức là số đoạn tạo ra phải ít nhất. Nếu xâu \(S\) đã đối xứng thì thầy không tính vết cắt nào cả.

Hãy giúp Tèo tìm số vết cắt tối thiểu cần thực hiện.

Đị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 các chữ cái Latin in thường.

Định dạng đầu ra

• In ra số vết cắt tối thiểu.

Ví dụ

Input:

aab

Output:

1

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.