← 返回题目列表

Codeforces · 1917/B

B. 删除第一个或第二个字母

中文机器翻译题面 查看原题

给定一个长度为 $$$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$$$。