Trong một lần thám hiểm tàn tích của một thư viện cổ, Kay tìm thấy một mảnh giấy kỳ lạ có chứa một thông điệp là một xâu gồm các kí tự chữ cái thường. Tưởng chừng xâu vô nghĩa nhưng Kay phát hiện một ghi chú ở góc mảnh giấy rằng "Đây là một phần của mật mã đối xứng được sử dụng bởi một tổ chức bí ẩn".

Đáng tiếc, qua thời gian, phần mật mã đã bị mất đi một số kí tự. Nhiệm vụ của bạn là khôi phục lại mật mã đối xứng này bằng cách chèn thêm ít kí tự nhất vào xâu kí tự mà Kay tìm được.

Dữ liệu vào:

Đọc từ file văn bản MATMA.INP một xâu S.

Dữ liệu ra:

Ghi ra file văn bản MATMA.OUT gồm một dòng duy nhất là số kí tự ít nhất cần chèn vào xâu S.

Ví dụ:

Input:
ab

Output:
1

Giải thích: Chỉ cần thêm 1 kí tự a hoặc b để tạo thành xâu đối xứng aba hoặc bab.

Input:
acbcd

Output:
2

Giải thích: Cần thêm 2 kí tự a và b để tạo thành xâu đối xứng adcbcda hoặc dacbcad.

Giới hạn:

- Subtask 1 (50%): độ dài của xâu S không vượt quá 255 kí tự.
- Subtask 2 (50%): độ dài của xâu S không vượt quá 10³ kí tự.