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\)