CodeCamp là hoạt động thường niên của IUH hằng năm dành cho các bạn trong đội tuyển Olympic Tin Học của trường. Lần này, thầy Tình dẫn các bạn đội tuyển lập trại code ở cao nguyên Tà Nung tại một Homestay nằm giữa rừng thông tại Đà Lạt.

Mọi thứ của trại code đều thuận lợi cho đến buổi sáng của ngày train team ICPC thứ 4, một cơn gió mùa Đông thổi qua rừng thông và làm cáp mạng bị đứt, mọi hoạt động train team đều dừng lại.

Trong lúc buồn chán chẳng thể submit bài giải, Trung đã dùng máy tính gen ra một xâu chữ cái và yêu cầu Ban hãy cho biết số thao tác xóa tối thiểu để xóa toàn bộ ký tự của xâu hiện tại với điều kiện mỗi thao tác xóa Ban chỉ được chọn và xóa một xâu con gồm các ký tự liên tiếp và xâu con đó phải là xâu đối xứng.

Là một người thích làm các bài quy hoạch động hơn các bài xâu, chính vì thế Ban đã tìm đến sự giúp đỡ của bạn. Bạn hãy giải bài toán này giúp Ban nhé.

Input

Một dòng duy nhất chứa xâu ~S~ ~(1 \leq |S| \leq 500)~ chỉ gồm các ký tự từ ~a~ đến ~z~ là xâu ký tự mà Trung đã gen ra.

Output

Một số nguyên duy nhất là số thao tác xóa tối thiểu để Ban có thể xóa toàn bộ ký tự của xâu ~S~.

Sample Input 1

icpciuh

Sample Output 1

3

Sample Input 1

bankngu

Sample Output 1

5

Giải thích

Ở test case 2, ban đầu ta có xâu ~S = bankngu~ ta sẽ xóa xâu con ~nkn~ thì ta được ~S = bagu~ sau đó ta xóa từng ký tự xâu này.