Statement : C. Red-Black Pairs

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?

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$.

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

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

RRBBBBRR