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 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ự gạch dưới sẽ được xóa để thu được xâu tiếp theo): ~aabbbacaa -> aabbbcaa -> aacaa -> caa -> aa ->~ " " 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 phép xóa: ~aabbbacaa -> aabbbaaa -> aaaaa ->~ " "

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.

Dữ liệu vào gồm:

• Dòng thứ nhất chứa số nguyên ~N~ là độ dài của xâu ~(1≤ n ≤ 1000)~
• Dòng thứ hai chứa xâu ~S~, mỗi kí tự chỉ gồm các chữ cái latin in thường (từ ~'a'~ đến ~'z'~)

Kết quả: 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.

Ví dụ:

INPUT

9
aabbbacaa

OUTPUT

3

Ràng buộc:

• Có 50% số test tương ứng 50% số điểm của bài có (1≤ N ≤ 100)
• Có 50% số test tương ứng 50% số điểm của bài có (100< N ≤ 1000)