Cho xâu ký tự \(S\) chỉ gồm các chữ cái latin in thường. Mỗi lần thực hiện, bạn được phép xóa một hoặc một dãy ký tự liên tiếp giống nhau khỏi xâu. Đối với xâu thu được sau khi ta lại có thể thực hiện phép xóa nói trên. Quá trình sẽ được tiếp tục như vậy cho đến khi thu được xâu rỗng.

Ví dụ: Cho xâu \(S = “aabbbacaa”\), ta có thể thực hiện xóa như sau (ở mỗi bước các ký tự được gạch dưới sẽ được xóa để thu được xâu tiếp theo):

\(aabbb \underline{a}caa \rightarrow aa \underline{bbb}caa \rightarrow \underline{aa}caa \rightarrow \underline{c}aa \rightarrow \underline{aa} \rightarrow “”\)

Cách xóa này đòi hỏi 5 lần thực hiện phép xóa. Cách xóa sau đây đòi hỏi 3 lần thực hiện xóa:

\(aabbba\underline{c}aa \rightarrow aa\underline{bbb}aaa \rightarrow \underline{aaaaa} \rightarrow “”\)

Yêu cầu: Hãy xác định cách xóa đòi hỏi ít lần thực hiện phép xóa nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) là độ dài của xâu \(S\) (\(1 < n < 1000\));
• Dòng thứ hai chứa xâu \(S\) gồm \(n\) ký tự, mỗi ký tự chỉ là chữ cái latin in thường (từ a đến z).

Output

• Ghi ra môt số nguyên là số phép xóa ít nhất cần thực hiện để xóa được tất cả các ký tự của xâu đã cho.

Example

9   
aabbbacaa   

3