1917B · Erase First or Second Letter

Problem: 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 Format: 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 Format: For each test case, output a single integer: the number of distinct non-empty strings you can get.

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