给定一个长度为 $$$n$$$ 的字符串 $$$s$$$。让我们定义两个可以应用于字符串的操作:
- 删除字符串的第一个字符;
- 删除字符串的第二个字符。
您的任务是找到通过以任意顺序对初始字符串任意次数(可能为零)应用给定操作可以生成的不同非空字符串的数量。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 字符串的长度。
每个测试用例的第二行包含字符串$$$s$$$。保证字符串只包含英文字母的小写字母。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:可以获得的不同非空字符串的数量。
示例
输入 #1
5 5 aaaaa 1 z 5 ababa 14 bcdaaaabcdaaaa 20 abcdefghijklmnopqrst
输出 #1
5 1 9 50 210
注意
在第一个测试用例中,我们可以得到以下字符串:$$$a$$$、$$$aa$$$、$$$aaa$$$、$$$aaaa$$$、$$$aaaaa$$$。
例如,在第三个测试用例中,可以通过以下方式访问单词 $$$ba$$$:
- 删除当前字符串$$$ababa$$$的第一个字符,得到$$$baba$$$;
- 删除当前字符串$$$baba$$$的第二个字符,得到$$$bba$$$;
- 删除当前字符串$$$bba$$$的第二个字符,得到$$$ba$$$。