Một palindrome là một chuỗi đối xứng, nghĩa là một chuỗi đọc giống hệt nhau từ trái sang phải cũng như từ phải sang trái. Bạn phải viết một chương trình cho một chuỗi, xác định số lượng ký tự tối thiểu được chèn vào chuỗi để có được một xâu palindrome.

Ví dụ, bằng cách chèn \(2\) ký tự, chuỗi Ab3bd có thể được chuyển đổi thành một palindrome (dAb3bAd hoặc Adb3bdA). Tuy nhiên, việc chèn ít hơn \(2\) ký tự không tạo ra một palindrome.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên: độ dài của chuỗi đầu vào \(N\) \((3 \le N \le 5000)\)
• Dòng thứ hai chứa một chuỗi có độ dài \(N\). Chuỗi được hình thành từ các chữ cái in hoa từ A đến Z, chữ thường từ a đến z và các chữ số từ 0 đến 9. Chữ in hoa và chữ thường được coi là khác biệt.

Dữ liệu ra

• Dòng đầu tiên chứa một số nguyên, là số tối thiểu mong muốn.

Input 1

5
ab3bd

Output 1

2