Minimum Moves to Palindrome Transformation

You are given a binary string s of length n. In one move, you can change one character in the string. The goal is to make the string a palindrome using the minimum number of moves. A string is a palindrome if it reads the same from left to right as from right to left.

More formally, let the number of mismatched indices in the first half compared with the corresponding character in the second half be c. Then, the minimum number of moves required is given by the formula $$\left\lceil \frac{c}{2} \right\rceil$$ which can be computed using integer arithmetic as (c+1)//2.

For example, for the binary string "11001" of length 5, there is 1 mismatched pair, so only 1 move is required, while if the string is already a palindrome, no moves are needed.

inputFormat

The first line contains a single integer t (the number of test cases). Each test case is described by two lines. The first line of each test case contains an integer n, the length of the binary string. The second line contains the binary string s of length n.

For example:

3
5
11001
4
1001
6
101011

outputFormat

For each test case, output a single integer – the minimum number of moves required to convert the binary string into a palindrome. Each answer should be printed on a separate line.

For example:

1
0
1

## sample

3
5
11001
4
1001
6
101011

1
0
1

</p>