★★飞马分隔符★★
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

非常喜欢FeiMa，如果一个字符串中存在一个子序列为FeiMa， 就会异常兴奋，然而这可能会导致一些无法预料的后果。
子序列为原字符串中删去若干字符，剩余字符相对位置不变形成的序列。例如ac，abcd均是abcd的子序列，而ca则不是abcd的子序列。

为了防止意外发生，你需要将这个字符串 按顺序划分为若干部分 ，且 ( 表示字符串的连接)，使得每一部分都不包含子序列FeiMa。而每次划分都需要一个“分隔符”，每个“分隔符”都要去商店购买。

现在，你想知道最少需要购买多少个分隔符。

输入描述:

第一行一个整数 ，表示测试用例的数量。
对于每组测试用例，第一行一个整数 ，表示字符串的长度；
接下来一行一个长度为  的字符串 。
对于全部测试用例，保证字符串  中仅包含大小写英文字母和数字且 。

输出描述:

对于每组测试用例，输出一行一个整数表示答案。
示例1

输入

复制 
2
18
FeiMa20210529FeiMa
5
MaFei

输出

复制 
2
0

说明

在第一组测试用例中，可将  分为 Fei、Ma20210529Fei、Ma，最少需要  个分隔符。
在第二组测试用例中，不需要分隔符。