小字节龙最近发现了一个很棒的游戏——用回形针制作链条。有一天，他用他父亲的回形针制作了一条长长的链条，然后去上学了。不幸的是，对于小字节龙来说，他的父亲需要所有的回形针。正如人们所预料的那样，他需要所有的回形针……并且是分开的。然而，在开始拆解儿子的作品之前，他想知道这需要多长时间。
父亲打算通过将一个回形针绕其垂直于桌面表面的轴旋转 $180^\circ$ 来解开链条。每次移动恰好需要一秒钟。下图展示了对小型回形针链条进行单次移动的过程。
↓
↓
↓
图 1： 解开链条过程中的最初几次移动。
请编写一个程序：
- 从标准输入读取链条的描述，
- 计算解开链条所需的最少移动次数，
- 将结果写入标准输出。
输入格式
链条由其连续回形针的排列方式以及每对相邻回形针之间的连接类型来描述。从上方观察放在桌子上的回形针时，我们可以看到它处于四种可能位置之一，如下图所示。
 |
 |
 |
 |
|---|---|---|---|
(A) |
(B) |
(C) |
(D) |
图 2： 回形针在桌子上的四种可能位置。
两个回形针有两种可能的连接方式——左侧回形针的顶部位于右侧回形针的顶部之上，反之亦然。
下图展示了这两种情况。
 |
 |
|
|---|---|---|
(P) |
(Q) |
图 3： 基于 BA 对展示的两种可能的回形针连接方式。
输入的第一行包含一个整数 $n$ ($2 \le n \le 5\,000\,000$)，表示回形针的数量。第二行包含链条的描述，由字母 A、B、C、D、P 和 Q 组成。这些字母代表回形针的排列方式以及连续回形针对的连接方式。
输出格式
输出的第一行也是唯一一行应包含一个整数，即拆解链条使其成为单个回形针所需的最少移动次数。
样例
输入 1
5 CPBQAPAPB
输出 1
4
说明
在样例中，初始链条看起来就像图 1 中的那样。如果采取与图中所示过程不同的操作方式，它可以在四次移动内被拆解。