1. 解题思路

本题要求统计子串数目：子串中必须包含五个主色字母各至少一次（D、M、T、A、O），且恰好包含 R 个其他辅助色。 直接双指针在“恰好”约束下较难计数，我们采用前缀和 + 最后出现位置 + 计数哈希的一次线性算法。

核心思想：

• 设主色集合 S = {D, M, T, A, O}。定义前缀数组 P[i] 表示前 i 个字符中出现的辅助色个数（P[0]=0）。 对任意子串 s[l..r]，辅助色个数为 P[r+1] - P[l]。若要恰好 R 个辅助色，则需 P[l] = P[r+1] - R。
• 为满足“五主色齐全”，对每个右端点 r，用 last[c] 记录五个主色各自的最后出现位置，若都出现过，则允许的左端点必须满足 l ≤ minLast，其中 minLast = min(last[D], last[M], last[T], last[A], last[O])。

题目内容

多多负责少女乐队演唱会的灯光部署，乐队成员都有各自神秘的艺名：Doloris(悲伤)、Mortis(死亡)、Timoris(恐惧)、Amoris(爱)、Oblivionis(忘却)。在乐队的演出中，舞台灯光系统有着独特的密码设定--五种主色灯光分别代表五位成员的艺名首字母($D、M、T、A、O$)，每场演出如果想要点亮舞台的最终特效,则灯光变换序列中必须包含全部五种主色(至少出现过一次)，并且恰好有 $R$ 个其他辅助色的灯光。

多多已经想好了一段灯光方案 $lightSequence$ , 请你帮多多求出其中有多少种子方案可以触发舞台的最终特效(子方案为原方案中截取的一段连续的序列)

输入描述

第一行为一个整数 $T$ , 表示共有 $T$ 个测试数据 $(1<=T<=10)$

每组测试数据：

第一行为一个整数 $R$ ,表示需要搭配的其他辅助色的灯光数目 $0<=R<=[lightSequence]-5)$

第二行为灯光方案序列 $lightSequence(1<=(lightSequence) <= 100000)$ ，

其中每个字符 $ci$ 表示灯光色号 ($'A'<=ci<'Z'$ ,仅包含大写字母)

输出描述

每组数据输出一个整数，表示能够触发舞台最终特效的子方案数量，每个结果占一行

样例1

输入

1
3
DAVMTTBLMO

输出

1

说明

只有一种子方案施触发最终特效：$DAVMTTBLMO$ , 其中 $V、B、L$ 是输入要求的恰好有的 $3$ 种辅助色，剩下的都是主色，且主色齐全

样例2

输入

1
0
DOAMT

输出

1

说明

只有一种子方案能触发最终特效：$DOAMT$ , 需要的辅助色为 $0$ ,方需中全是主色，且主色齐全

样例3

输入

1
1
OYOMAOTD

输出

2

说明

触发最终特效的子方案有两种：$OYOMAOTD、YOMAOTD$，恰好有 $1$ 个输入要求的辅助色 $Y$，剩下的都是主色，且主色齐全