题目描述

你有一条长度为 $n$ 的空白木板，需要把它涂成目标颜色，目标颜色用一个长度为 $n$ 的字符串表示。

每次操作可以把一段连续的木板涂成同一种颜色，后涂的颜色会覆盖先涂的颜色。

例如，目标为 $\texttt{RGBGR}$ ，一种涂法为：先把整条涂成 $\texttt{RRRRR}$ ，再把第 2-4 格涂成 $\texttt{GGG}$ 得到 $\texttt{RGGGR}$ ，最后把第 3 格涂成 $\texttt{B}$ 得到 $\texttt{RGBGR}$ ，共 3 次。

求用最少的操作次数达到目标。

输入格式

输入一行，包含一个长度为 $n$ 的字符串，表示涂色目标。字符串中每个字符都是大写字母，相同字母代表相同颜色，不同字母代表不同颜色。

输出格式

输出一行，包含一个整数，表示最少的涂色次数。

样例

AAAAA

1

RGBGR

3

提示

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

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