Dải lụa màu

Cho một dải lụa có độ dài \(n\). Bạn có thể tô một đoạn liên tiếp trên dải lụa bằng một trong \(26\) màu tương ứng với các chữ cái viết thường (một lần tô sau có thể đè lên màu đã tô trước đó). Ban đầu dải lụa không có màu nào. Hãy tìm cách sử dụng số lần tô ít nhất để dải lụa có màu tương ứng với xâu \(S\).

Input

• Một dòng gồm xâu \(S\) chỉ gồm các chữ cái viết thường, có độ dài \(n\) \((1 \le n \le 500)\).

Output

• In ra một số nguyên là số lần tô màu ít nhất.

Input

%
abcba

Output

%
3

Notes

Với $S = abcba$, một cách tô tối ưu gồm ba lần: tô màu a lên toàn bộ dải được aaaaa; tô màu b lên đoạn giữa được abbba; cuối cùng tô màu c lên ô ở giữa được abcba. Không thể làm với ít hơn ba lần tô, nên đáp án là \(3\).

Scoring

• (\(40\%\)) \(1 \le n \le 10\);
• (\(30\%\)) \(1 \le n \le 100\);
• (\(30\%\)) \(1 \le n \le 500\).