Description

Input

The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Following that are the descriptions of the test cases.

The first line of each test case contains an integer $n$ ($2 \le n \le 50$) — the length of the melody $s$.

The second line of each test case contains a string $s$ of length $n$, consisting of characters 'a', 'b', 'c', 'd', 'e', 'f', 'g'.

Output

Output $t$ integers, each representing the answer for the corresponding test case. As the answer output minimum number of melodies consisting of two notes that Vlad needs to record.

5
4
abab
7
abacaba
6
aaaaaa
7
abcdefg
5
babdd
 
 
 
 
 
 

2
4
1
6
4

Note

In the first sample, you need to record the melodies "ab" and "ba", as described in the problem statement.

In the second sample, you need to record the melodies "ab", "ba", "ac", and "ca".

In the third sample, the only necessary melody is "aa".