Tý có một xâu \(S\) độ dài \(N\). Bạn muốn cắt xâu thành nhiều đoạn liên tiếp sao cho mỗi đoạn là một xâu đối xứng. Hãy tìm số lần cắt ít nhất cần thực hiện.

#

Định dạng đầu vào

• Một dòng chứa xâu \(S\) gồm các chữ cái tiếng Anh in thường (\(1 \le |S| \le 2000\)).

Định dạng đầu ra

• In ra số nhát cắt tối thiểu để chia xâu \(S\) thành các đoạn đều là palindrome.

Ví dụ

Input:

aab

Output:

1

Giải thích: Cắt tại vị trí 2: aa | b (1 nhát cắt).

Ràng buộc & Subtasks