Description

兔子是「兔兔建设」的社长。最近公司的建设进度不如预期，经过兔子社长的调查后，发现原因出在负责运送油漆的粽子离职了！于是兔子社长决定雇用猩猩来完成原本粽子的工作。另外，在调查过程中兔子社长还发现，假如能在油漆搬运抵达之后将其进行分类，可以进一步提升装潢部门的效率。于是兔子社长借此机会，也将此任务安排给猩猩来完成。

根据规定，搬运完成的油漆桶会被摆放成一列。由于油漆桶非常重，猩猩每次只能将两桶相邻的油漆交换位置。兔子社长给猩猩的要求是将所有相同颜色的油漆桶摆在一起。举例来说，假设油漆总共有 7 桶，其颜色分为红绿蓝三种，分别以 R、G、B 表示，而初始时此 7 桶油漆从左到右的排列为：RRGGBGB，则猩猩只需要一次操作，便能把油漆桶排列为 RRGGGBB。又若初始时油漆桶的排列为：GRRGBRB，则猩猩最少只要三次操作，便能把油漆桶排列为 GGRRRBB。

狡猾的兔子社长决定根据完成任务所需最少的交换次数来支付猩猩的薪水，假如给定油漆桶初始的排列，你能帮助猩猩算出最少的交换次数，来估计她应得的薪水吗？

Input Format

• $S$ 为一个字符串，代表油漆桶的排列顺序，其中相同字符表示相同颜色的油漆桶，不同字符代表不同颜色。

Output Format

• $m$ 代表最少的交换次数。

RRGGBGB

1

GRRGBRB

3

aAaaAaa

4

Hint

数据限制

• $1 \le |S| \le {10}^{6}$。
• $1 \le \textrm{distinct}(S) \le 7$。
• 字符串 $S$ 由大小写英文字母组成。
• $\textrm{distinct}(S)$ 代表字符串 $S$ 中字符种类的数量。

评分说明

本题共有三组子任务，条件限制如下所示。 每一组可有一或多笔测试数据，该组所有测试数据皆需答对才会获得该组分数。