该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

科比在观看自己的比赛录像时，发现每一次进攻都让他心潮澎湃，忍不住肘击。录像的字幕由一个字符串组成，科比将其中以“Mamba”开头并以“out”结束的连续一段子串（子串是指字符串中连续字符构成的子序列）称为“曼巴时刻”。 现在给定一个长字符串（由大写或小写字母组成，长度$≤ 2 \cdot 10^{5}$），请你找出所有“曼巴时刻”子串的数量。如果两个子串在文本中的起始或结束位置不同，则视为不同子串。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量$t(1≤t≤1000)$。

每个测试用例的第一行都包含一个整数$n$，表示字符串的长度。$(1 ≤ n ≤ 2 \cdot 10⁵)$。

每个测试用例的第二行都包含一个长度为$n$的字符串。

每个测试$n$的总和不超过$2 \cdot 10^{5}$，且字符串均为小写字母或者大写字母。

输出格式

对于每个测试用例，输出一个整数，表示“曼巴时刻”子串的数量。（每个测试用例结尾必须输出一个换行符）

样例

3
18
MambaoutisMambaout
13
Mambaoutisout
78
trueMambaoutissotruewellitisalsosoMambathatyoucanalmostfeeltheweightofoutonyou

3
2
3

样例解释

对于第一组样例：

字符串 MambaoutisMambaout 中：

Mambaout（第一个 “Mamba” 到第一个 “out”）

整个字符串（第一个 “Mamba” 到最后一个 “out”）

第二个 Mambaout（第二个 “Mamba” 到最后一个 “out”）

总共 $3$ 个符合条件的子串，所以输出 $3$。

对于第二组样例：

字符串 Mambaoutisout 中：

Mambaout（第一个 “Mamba” 到第一个 “out”）

整个字符串（第一个 “Mamba” 到最后一个 “out”）

总共 $2$ 个符合条件的子串，所以输出 $2$。

对于第三组样例：

字符串trueMambaoutissotruewellitisalsosoMambathatyoucanalmostfeeltheweightofoutonyou 中：

第一个 “Mamba” 与它后面的第一个 “out” 组成一个子串

第一个 “Mamba” 与末尾的 “out” 组成一个子串

第二个 “Mamba” 与末尾的 “out” 组成一个子串

总共 $3$ 个符合条件的子串，所以输出 $3$。