310984: CF1917B. Erase First or Second Letter

B. Erase First or Second Lettertime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string $s$ of length $n$. Let's define two operations you can apply on the string:

• remove the first character of the string;
• remove the second character of the string.

Your task is to find the number of distinct non-empty strings that can be generated by applying the given operations on the initial string any number of times (possibly zero), in any order.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains $n$ ($1 \leq n \leq 10^5$) — the length of the string.

The second line of each test case contains the string $s$. It is guaranteed that the string only contains lowercase letters of the English alphabet.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer: the number of distinct non-empty strings you can get.

ExampleInput

5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst

Output

5
1
9
50
210

Note

In the first test case, we can get the following strings: $a$, $aa$, $aaa$, $aaaa$, $aaaaa$.

In the third test case, for example, the word $ba$ can be reached in the following way:

• remove the first character of the current string $ababa$, getting $baba$;
• remove the second character of the current string $baba$, getting $bba$;
• remove the second character of the current string $bba$, getting $ba$.

题目大意：
给定一个长度为n的字符串s，你可以进行两种操作：删除字符串的第一个字符或删除第二个字符。任务是通过任意次数（可能为零）的给定操作，以任意顺序生成不同的非空字符串的数量。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含n（1≤n≤10^5），表示字符串的长度。
每个测试用例的第二行包含字符串s。保证字符串只包含小写英文字母。
保证所有测试用例的n之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个整数：可以得到的不同的非空字符串的数量。

例：
输入
```
5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst
```
输出
```
5
1
9
50
210
```

注意：
在第一个测试用例中，我们可以得到以下字符串：a, aa, aaa, aaaa, aaaaa。
在第三个测试用例中，例如，单词ba可以通过以下方式得到：
- 删除当前字符串ababa的第一个字符，得到baba；
- 删除当前字符串baba的第二个字符，得到bba；
- 删除当前字符串bba的第二个字符，得到ba。题目大意： 给定一个长度为n的字符串s，你可以进行两种操作：删除字符串的第一个字符或删除第二个字符。任务是通过任意次数（可能为零）的给定操作，以任意顺序生成不同的非空字符串的数量。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含n（1≤n≤10^5），表示字符串的长度。 每个测试用例的第二行包含字符串s。保证字符串只包含小写英文字母。 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数：可以得到的不同的非空字符串的数量。 例： 输入 ``` 5 5 aaaaa 1 z 5 ababa 14 bcdaaaabcdaaaa 20 abcdefghijklmnopqrst ``` 输出 ``` 5 1 9 50 210 ``` 注意： 在第一个测试用例中，我们可以得到以下字符串：a, aa, aaa, aaaa, aaaaa。 在第三个测试用例中，例如，单词ba可以通过以下方式得到： - 删除当前字符串ababa的第一个字符，得到baba； - 删除当前字符串baba的第二个字符，得到bba； - 删除当前字符串bba的第二个字符，得到ba。