1194 - 修改字符串
Description

给定一个由 ABC 三种字符构成的字符串，问最少改动多少个位置的字符，使得最终的字符串满足任意两个相邻的字符都不同。

字符串长度 ≤10^6


Input

一行一个字符串。

Output

一行一个整数表示答案。

Examples

Input

ABCBA

Output

0
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 2
通过次数 1
讨论
题解
统计
上一题
下一题