You are given a string $S$ of $N$ characters comprising of $A's$ and $B's$. You can choose any index $i$ and change $S_i$ to either $A$ or $B$.

Find the minimum number of changes that you must make to string $S$ such that the resulting string is of the following format:

 $\underbrace{AAAA........}_\text{$x$ number of $A's$} \underbrace{BBBB........}_\text{$n-x$ number of $B's$}$       

where $0 \le x \le n$

In other words, your task is to determine the minimum number of changes such that string $S$ has $x$ number of $A's$ in the beginning, followed by the remaining $(n-x)$ number of $B's$.

Input format

• First line: A single integer $T$ denoting the number of test cases
• For each test case:
  • First line contains a single integer $N$ denoting the size of the string
  • Second line contains string $S$

Output format

For each test case, print a single line containing one integer that represents the minimum number of changes you need to make in string $S$ as mentioned in the question.

Constraints

$1 \le T \le 10^4\\ 1 \le N \le 10^6$

Note: Sum of $N$ overall test cases does not exceed $5\times 10^6$