C. Red-Black Pairs
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

There is a table of $$$2 \times n$$$ cells. Each cell of the table is colored either red or black. You want to repaint some cells of this table so that there exists at least one way to partition all cells into $$$n$$$ pairs such that the following conditions hold:

  • the cells in each pair have the same color;
  • the cells in each pair share a side.

What is the minimum number of cells that need to be repainted?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^{5}$$$).

The second and third lines of each test case describe the colors of the cells. Each line contains a string consisting of exactly $$$n$$$ letters "R" and/or "B".

Additional constraint on the input:

  • the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output

For each test case, output one integer — the minimum number of cells that need to be repainted.

Example
Input
5
1
R
B
2
BR
BR
3
RBR
BRB
4
RRBB
BBRB
5
RBRBR
BBBRB
Output
1
0
3
1
4
Note

Consider the $$$3$$$rd example. One possible option is to color all cells in one color, which requires repainting $$$3$$$ cells.

In the $$$4$$$th example, one possible valid repainting is 


RRBB
BBRR