K. Yet Another Swap Task
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Fankoush has successfully been recruited as the advisor to Sultan Malik.

In his first day, he faced a new challenge: Sultan Malik has an ancient letter containing an encrypted string $$$S$$$ of $$$N$$$ characters. The letters hold some important content. To restore it, the string must be sorted through a series of swaps.

Again, there is a restriction: characters $$$c_1$$$ and $$$c_2$$$ can only be swapped if a rule $$$(c_1, c_2)$$$ exists. At first, no rules exist, so Fankoush must create them.

Note that the rule $$$(c_1, c_2)$$$ is the same as the rule $$$(c_2, c_1)$$$.

To prove his skill, he must find the minimum number of rules required to sort the string in ascending order.

Fankoush is tired of sorting stuff for Malik, so he asked for your help again.

Input

The first line contains an integer $$$T$$$, the number of test cases $$$( 1 \le T \le 10^5 )$$$. For each test case:

  • The first line contains an integer $$$N$$$, the length of the string $$$( 2 \le N \le 10^5 )$$$.
  • The second line contains a string $$$S$$$ of length $$$N$$$ of lowercase letters.
It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$3.10^5$$$.
Output

Print the minimum number of rules. It can be proven that a solution always exists.

Example
Input
4
2
ab
2
ba
3
cba
3
cab
Output
0
1
1
2