H. Litmus Test
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a list of $$$n$$$ aqueous chemicals, each known to be either an acid, a base, or a salt. You have to prove the type of each chemical using litmus papers.

There are two types of litmus papers:

  • Red litmus paper: turns blue when exposed to a base; remains red in acid or salt.
  • Blue litmus paper: turns red when exposed to an acid; remains blue in base or salt.

To prove a chemical's type, you must test it in a way that rules out all other possibilities. In other words, the result must be enough to uniquely confirm that the chemical is acid, base, or salt.

You may reuse a single litmus paper multiple times (even on the same chemical). When a litmus paper changes color (e.g., red to blue), you can continue using it in its new color state until it changes color again. For example, if a red litmus paper turns blue after testing a base, you can use this blue paper to test other chemicals until it turns red again, and then, similarly, continue reusing it if needed. You may safely assume that the effect of contamination from earlier tests on the same paper is negligible.

Your task is to compute the minimum total number of litmus papers required to verify all the given chemicals. It doesn't matter how many times you use each individual litmus paper; you only want to minimize the total count of litmus papers used.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of chemicals.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$ consisting only of the characters A, B, and S, where the $$$i$$$-th character of $$$s$$$ represents the type of the $$$i$$$-th chemical — A represents an acid, B represents a base, and S represents a salt.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum total number of litmus papers required.

Example
Input
6
5
AAAAA
2
AB
1
S
4
SSBB
4
BASS
5
AAAAB
Output
5
1
2
2
1
1
Note

In the first test case, we use one fresh blue litmus paper for each chemical. Each paper turns red, confirming that all chemicals are acid.

In the second test case, we use a red litmus paper on the second chemical. It turns blue, confirming the chemical is base. We then use the same litmus paper, now blue, on the first chemical and it turns red, confirming the chemical is acid.

In the third test case, we use a red and a blue litmus paper on the chemical. Neither changes color, confirming that the chemical is salt.

In the fourth test case, we use two red litmus papers on the first two chemicals. Both papers remain red, indicating the chemicals are either acid or salt. We then use the same papers on the next two chemicals. Both turn blue, confirming that those chemicals are base. Finally, we reuse the now-blue litmus papers on the first two chemicals. Both remain blue, confirming that the first two chemicals are salt.