codeforces#P1917B. Erase First or Second Letter

    ID: 34325 远端评测题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 3 上传者: 标签>brute forcecombinatoricsdata structuresdpstrings*1100

Erase First or Second Letter

Description

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.

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$.

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

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.

5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst
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$.