题目描述

噜噜最近和黑大帅闹矛盾了，最近很不喜欢看到字符串 HDS。

现在YZY给了他一个长度为 $n$ 的字符串，这个字符串中的每个字符只可能是 H、D、S 三种字母之一。

噜噜希望你通过修改一些位置上的字符，使得修改后的整个字符串中 不出现连续子串 HDS。

你每次可以进行如下操作之一：

• 将某一个位置上的字符改成 H、D、S 中的任意一个其他字符。

注意：

• 只能修改字符，不能删除字符，也不能插入字符。

请你求出，最少需要修改多少个位置，才能使得字符串中不存在子串 HDS。

输入格式

• 第一行输入一个整数 $n$。

• 第二行输入一个长度为 $n$ 的字符串 $s$，保证其中每个字符都只可能是 H、D、S。

输出格式

• 输出一个整数，表示最少需要修改的字符个数。

4  
HDSH

1

说明

将第 $3$ 个字符 S 改成 H，字符串变为 HDHH，此时不再出现子串 HDS。

5  
HDSSD

1

说明

原串中第 $1\sim 3$ 个字符构成 HDS，只需修改其中任意一个字符即可。

数据范围