小 A 非常喜欢粉刷，他喜欢把栅栏刷成五彩斑斓的颜色。

小 A 的栅栏，由若干块大小相同的还没粉刷过的木板组成。如果小 A 想把栅栏刷成红、绿、蓝、绿、红色，可以使用字符串\texttt{RGBGR}，来表示小 A 的粉刷目标。

小 A 的粉刷方式比较独特，他每次粉刷会将一段连续的木板涂成同一个给定的颜色。比如，为了实现上面的粉刷目标，他可以第一次将木板都粉刷成\texttt{RRRRR}，第二次粉刷成 \texttt{RGGGR}，第三次粉刷成 \texttt{RGBGR}，这样一来，只需要 3 次粉刷，就可以实现自己的粉刷目标。

给定一个小 A 的粉刷目标，请问按照他独特的粉刷方式，最少需要多少次，可以实现自己的粉刷目标。

输入一行仅包含大写字母的字符串，表示小 A 栅栏的粉刷目标。

字符串中的每个大写字母表示小 A 栅栏中某块木板上的一个颜色，如果字母相同代表颜色相同，否则代表颜色不同。

输出小 A 最少的粉刷次数。

【数据范围】

栅栏的长度为 n。

40\% 的数据满足 1\le n\le 10。

100\% 的数据满足 1\le n\le 50。

区间动归