Cho một xâu ~s~ chỉ gồm chữ cái thường. Mỗi lượt được xóa một ký tự bất kỳ. Hãy tìm số lượt xóa ít nhất để xâu còn lại là palindrome.

Input

Một xâu ~s~ có độ dài từ 1 đến 2000.

Output

In ra số ký tự cần xóa ít nhất.

Subtask

• 100% số điểm: không có ràng buộc bổ sung ngoài các giới hạn đã nêu ở phần Input.

Ví dụ 1

abcca

1

Ví dụ 2

abacda

3