You and she are playing a game.

You and she each have $n$ ordered cards, and each card can be pink, purple, or white.

Starting with her, you and she take turns playing your cards in the order they appear. The played cards are moved to a pile.

If, after someone plays a card, the number of cards of each of the three colors in the pile is equal, that person wins and the game ends. If both of you have played all your cards and no one has won, the game is a draw.

Before the game starts, you can perform any number of operations. In each operation, you can change the color of any card belonging to either person.

You want to find the minimum number of operations required to make her win. It can be proven that there always exists at least one strategy to make her win.

Input

The input contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

Each test case is described as follows:

• The first line contains a positive integer $n$.
• The second line contains a string $s$ of length $n$, describing her cards:
  • If $s_i$ is P, her $i$-th card is pink;
  • If $s_i$ is V, her $i$-th card is purple;
  • If $s_i$ is W, her $i$-th card is white.
• The third line contains a string $t$ of length $n$, describing your cards:
  • If $t_i$ is P, your $i$-th card is pink;
  • If $t_i$ is V, your $i$-th card is purple;
  • If $t_i$ is W, your $i$-th card is white.

Here, $s_i$ denotes the $i$-th character of string $s$, and $t_i$ is defined similarly.

Output

For each test case, output a single integer representing the minimum number of operations required to make her win. If she can win without any operations, output $0$.

It can be proven that there always exists at least one strategy to make her win.

Constraints

For all test cases, it is guaranteed that:

• $1 \le T \le 30$;
• $2 \le n \le 10^5$;
• For all $1 \le i \le n$, $s_i$ and $t_i$ are characters from PVW.

This problem uses bundled testing.

• Subtask 1 (18 points): $n \le 6$.
• Subtask 2 (20 points): $n \le 1000$.
• Subtask 3 (12 points): For all $1 \le i \le n$, $s_i \ne t_i$.
• Subtask 4 (25 points): If you do not perform any operations, you will not win.
• Subtask 5 (25 points): No additional constraints.

Examples

Input 1

3
2
PW
VP
5
PPWWP
PWVWV
6
WVPPWW
VVPVWP

Output 1

0
2
1

Note 1

For the first test case, she can win without any operations.

For the second test case, one possible strategy is to change the color of her 4th and 5th cards to purple.

For the third test case, one possible strategy is to change the color of your 4th card to white.