Giải bài trực tuyến

Given a string containing only characters of 'a' and 'b'. You can reduce this string by replacing a substring forming a?a or b?b by ?; ? is 'a' or 'b'.

Request

Find a way to minimize the length of given string by reducing it. Output that minimum length.

Input

- A string.

Output

- The minimum length found.

Example

Input:
baaba

Output:
1

Limitations

- The length of the given string does not exceed 300.