题目描述

如果一个数字字符串中每个字符的出现次数不超过字符种类的数量，则该字符串是多样的。

例如：

字符串“7”是多样的，因为7出现在其中1次，其中的字符种类数为1；

字符串“77”不多样，因为7出现在其中2次，其中的字符种类数为1；

字符串“1010”是多样的，因为0和1都出现在其中2次，其中的字符种类数为2；

字符串“6668”并不多样，因为6出现在其中3次，其中的字符种类数为2。

给你一个长度为n的字符串s，仅由0到9位数字组成。找出它的$n*（n+1）/2$个子字符串中有多少是不同的。

如果可以通过删除开头的几个（可能为零或全部）字符和结尾的几个（也许为零或所有）字符从b中获得A，则字符串A是字符串b的子字符串。

注意，如果同一个不同的字符串多次出现在s中，则每次出现都应单独计数。例如，“77”中有两个不同的子字符串，都等于“7”，因此字符串“77”的答案是2。

输入描述

每个测试包含多个测试用例。第一行包含单个整数$t（1≤t≤10^4）$-测试用例的数量。

每个测试用例的第一行包含单个整数$n（1≤n≤10^5）$-字符串的长度。

每个测试用例的第二行包含长度为n的字符串s。保证s的所有字符都是从0到9的数字。

保证所有测试用例的n之和不超过$10^5$。

输出描述

对于每个测试用例，打印一个整数-给定字符串s的不同子字符串的数量。

输入输出样例

7
1
7
2
77
4
1010
5
01100
6
399996
5
23456
18
789987887987998798

1
2
10
12
10
15
106

提示

在第一个测试用例中，多样的子字符串是“7”。

在第二个测试用例中，唯一多样的子字符串是“7”，它出现了两次，因此答案是2。

在第三个测试用例中，多样的子字符串是“0”（2次）、“01”、“010”、“1”（2）、“10”（2倍）、“101”和“1010”。

在第四个测试用例中，多样的子字符串是“0”（3次）、“01”、“011”、“0110”、“1”（2次）、”10“、”100“、”110“和”1100“。

在第五个测试用例中，不多样的子字符串是“3”、“39”、“399”、“6”、“9”（4次）、“96”和“996”。

在第六个测试用例中，“23456”的所有15个非空子字符串都是多样的。