問題文

いま、電光掲示板に a・b・c からなる長さ N の文字列 S が表示されています。

あなたは以下の 2 種類の操作を好きな順番で何回でも行うことができます。ただし「変化させる」とは、元々 a だったものを b に、b だったものを c に、c だったものを a に変えることを指します。

• S_i = b である i (1 \leq i \leq N) を 1 つ選び、S_i を a に変更した後、S_1, S_2, \cdots, S_{i-1} を変化させる。
• S_i = c である i (1 \leq i \leq N) を 1 つ選び、S_i を b に変更した後、S_1, S_2, \cdots, S_{i-1} を変化させる。

最大で何回の操作が行えるか、求めてください。

制約

• 1 \leq N \leq 60
• S は a・b・c からなる長さ N の文字列である

入力例 1

3
aba

出力例 1

2

例えば以下のような手順をとることで、2 回の操作を行うことができます。

• まず i = 2 を選んで操作を行う。そのとき、文字列 S は aba → baa に変化する。
• 次に i = 1 を選んで操作を行う。そのとき、文字列 S は baa → aaa に変化する。

入力例 2

10
aaaaaaaaaa

出力例 2

0

すべての文字が a であるため、残念ながら操作を行うことができません。

入力例 3

5
baaca

出力例 3

17