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ỗi lần tô sẽ phủ đè lên các lớp màu tô trước đó trong đoạn đó). 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 duy nhất chứa xâu \(S\) (\(1 \le n = |S| \le 1000\)) chỉ gồm các chữ cái viết thường.

Output

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

Example

Input:

abcba

Output:

3

Note

• Lần tô đầu tiên tô màu a từ vị trí \(1\) đến \(5\): aaaaa.
• Lần tô thứ hai tô màu b từ vị trí \(2\) đến \(4\): abbba.
• Lần tô thứ ba tô màu c ở vị trí \(3\): abcba.