有两个煤矿，每个煤矿都雇佣了一组矿工。采煤工作很辛苦，所以矿工需要食物来维持体力。每当有一批食物运送到他们的矿井时，矿工就会生产一定数量的煤。食物共有三种：肉类、鱼类和面包。

矿工喜欢饮食多样化，如果食物供应保持多样，他们的生产效率会更高。更准确地说，每当有一批新货物运送到他们的矿井时，他们会考虑这批新货物以及之前的两批货物（如果不足两批，则考虑所有已有的货物），然后：

• 如果所有货物类型相同，他们将生产 1 单位的煤。
• 如果货物中包含两种不同的类型，他们将生产 2 单位的煤。
• 如果货物中包含三种不同的类型，他们将生产 3 单位的煤。

我们预先知道食物货物的类型以及它们发送的顺序。可以通过决定将哪批货物发送到哪个矿井来影响煤的产量。货物不能拆分；每批货物必须完整地发送到其中一个矿井。

两个矿井不一定非要接收相同数量的货物（实际上，允许将所有货物发送到同一个矿井）。

题目描述

给定食物货物的类型及其发送顺序，编写一个程序，通过决定将每批货物发送到矿井 1 还是矿井 2，找出可以生产的煤的最大总产量。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)，表示食物货物的数量。

第二行包含一个长度为 $N$ 的字符串，表示货物按发送顺序排列的类型。每个字符都是大写字母 'M'（代表肉类）、'F'（代表鱼类）或 'B'（代表面包）。

输出格式

输出一个整数，表示可以生产的煤的最大总产量。

子任务

在总分 45 分的测试用例中，货物数量 $N$ 最多为 20。

样例

输入 1

6
MBMFFB

输出 1

12

说明 1

在左侧样例中，通过按以下顺序分配货物：矿井 1、矿井 1、矿井 2、矿井 2、矿井 1、矿井 2，货物将依次产生 1、2、1、2、3 和 3 单位的煤，总计 12 单位。还有其他方法可以达到这个最大值。

输入 2

16
MMBMBBBBMMMMMBMB

输出 2

29