Bajtocki Lotek 公司专门从事数字游戏和金钱彩票，其中最受欢迎的是名为 字母游戏 的彩票。Bajtazar 也决定在游戏中试试运气。

字母游戏 的彩票包含 $n$ 个位置。每个位置都可以圈选 A、B 或 C 三个字母中的一个。下图显示了 $n = 10$ 时彩票的示例填写：

中奖者通过一台抽奖机进行抽取，抽奖机中有 $3n$ 个三种类型的金属球：$n$ 个带字母 A 的球，$n$ 个带字母 B 的球和 $n$ 个带字母 C 的球。机器顶部均匀分布着 $n$ 个直径小于球直径的孔。在抽奖的某个时刻，气动机构被激活，导致每个孔都吸住一个球。依次写出抽到的球上的字母，就得到一个由 $n$ 个字母组成的序列，即为抽奖结果。那些彩票上圈选了相同字母序列的幸运拥有者将获得大奖——一百万 Bajtalar 奖金。图中显示了上述彩票能获得大奖的抽奖结果。

Bajtazar 购买了一张彩票并在上面圈选了 $n$ 个字母。然而，在他还没来得及把彩票交到销售点之前，媒体就爆料称 字母游戏 的抽奖并非完全公平。经调查发现，相同类型的球——即带有相同字母的球——会相互排斥，并且在抽奖过程中绝不会排列在相邻的孔中（例如，上图中所示的球排列是不可能的）。

Bajtazar 得知此事后，决定修改他圈选的 $n$ 个字母序列，使得序列中没有两个连续的字母是相同的。为了不冒险，他希望尽可能少地更改序列中的字母。帮助 Bajtazar 确定他需要更改多少个字母。

Input Format

输入的第一行包含一个整数 $n$（$2 \le n \le 500,000$）。第二行包含一个由 $n$ 个字符 A、B 和/或 C 组成的序列。此序列中至少存在一对相邻的相同字母。

Output Format

输出的第一行也是唯一一行应包含一个正整数——序列中需要更改的最少字母数，以便没有任何两个相同的字母相邻。

Examples

Input

10
BAACBBAAAC

Output

3