题目内容

给定一个长度为 $n$、仅由小写字母组成的字符串 $t$。称一个非空子串是均衡的，当且仅当在该子串中，所有出现过的字母的出现次数都相等。请计算 $t$ 中均衡子串的总数。

对于每个测试用例，$n$ 不超过 $2000$。所有测试用例的 $n$ 总和不超过 $2080$。$1 \le T \le 100$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来对于每组数据： 第一行包含一个整数 $n$，表示字符串长度。 第二行包含一个长度为 $n$、仅由小写字母组成的字符串 $t$。 保证所有测试数据中 $n$ 的总和不超过 $2080$。

输出描述

对于每组测试数据，输出一行一个整数，表示该字符串中均衡子串的数量。

样例1

输入

1
1
z

输出

1

说明

$n=1$，字符串为 z。其唯一的非空子串是 z，该子串中仅出现字母 z，出现次数为 $1$。根据定义，所有出现过的字母只有 z，出现次数相等，因此该子串是均衡的。答案为 1。

样例2

输入

1
4
aaaa

输出

10

说明

$n=4$，字符串为 aaaa。该字符串的任意非空子串均只包含字母 a，设子串长度为 $k$，则 a 的出现次数即为 $k$，所有出现过的字母（只有 a）出现次数自然相等，故所有非空子串均为均衡子串。长度为 $4$ 的字符串共有 $\frac{4\times5}{2}=10$ 个非空子串，因此答案为 10。

样例3

输入

1
5
aabbb

输出

11

说明

$n=5$，字符串为 aabbb。均衡子串共 11 个：长度为 $1$ 的子串全部均衡，有 5 个（a, a, b, b, b）；长度为 $2$ 的均衡子串有 aa、ab、bb、bb，共 4 个；长度为 $3$ 的均衡子串只有 bbb，共 1 个；长度为 $4$ 的均衡子串只有 aabb，共 1 个；长度为 $5$ 的 aabbb 中 a 出现 $2$ 次、b 出现 $3$ 次，不均衡。总数为 $5+4+1+1=11$。