Một xâu đối xứng là xâu đọc từ trái sang phải hay từ phải sang trái đều giống nhau. Cho một xâu, hãy xác định số ký tự ít nhất cần chèn vào xâu để thu được một xâu đối xứng.

Ví dụ, bằng cách chèn \(2\) ký tự, xâu Ab3bd có thể trở thành xâu đối xứng dAb3bAd hoặc Adb3bdA. Không thể thu được xâu đối xứng bằng cách chèn ít hơn \(2\) ký tự.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), độ dài xâu, với \(3 \le N \le 5000\). Dòng thứ hai chứa xâu có đúng \(N\) ký tự. Mỗi ký tự là chữ cái in hoa từ A đến Z, chữ cái thường từ a đến z, hoặc chữ số từ 0 đến 9. Chữ hoa và chữ thường được xem là khác nhau.

Dữ liệu ra

In một số nguyên là số ký tự ít nhất cần chèn.

Ví dụ

5
Ab3bd

2