B. Erase First or Second Letter
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard 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.

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