Cho một xâu \(S\). Ở mỗi bước, bạn có thể chèn \(1\) ký tự tùy ý vào bất kỳ vị trí nào trong xâu \(S\). Hãy tính số bước ít nhất cần thực hiện để biến \(S\) thành xâu đối xứng.

Dữ liệu vào

• Một xâu \(S\) \((1 \le |S| \le 5000)\)

Dữ liệu ra

• Số bước ít nhất cần thực hiện để biến \(S\) thành xâu đối xứng.

Input 1

lmevxeyzl

Output 1

4