Problem Description

You and she are playing a game.

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

She goes first. You and she take turns, and each person must play the cards in order. The played card will be moved into the pile.

If, after someone plays a card, the numbers of cards of the three colors in the pile are the same, then that person wins and the game ends. If both you and she have finished playing all cards and no one has won, then the game is a draw.

Before the game starts, you may perform some operations. In each operation, you may change the color of any one card of either person.

You want to find the minimum number of operations needed to make her win. It can be proven that there is always at least one way to make her win.

Input Format

This problem has multiple test cases.

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

Then the test cases follow. For each test case:

• 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, then her $i$-th card is pink.
  • If $s_i$ is V, then her $i$-th card is purple.
  • If $s_i$ is W, then her $i$-th card is white.
• The third line contains a string $t$ of length $n$, describing your cards:
  • If $t_i$ is P, then your $i$-th card is pink.
  • If $t_i$ is V, then your $i$-th card is purple.
  • If $t_i$ is W, then your $i$-th card is white.

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

Output Format

For each test case, output one integer per line: the minimum number of operations required to make her win. If she can win without any operation, output $0$.

It can be proven that there is always at least one valid operation plan that makes her win.

3
2
PW
VP
5
PPWWP
PWVWV
6
WVPPWW
VVPVWP

0
2
1

Hint

"Sample Explanation #1"

For the $1$-st test case, no operation is needed for her to win.

For the $2$-nd test case, one possible plan is to change the colors of her $4$-th and $5$-th cards to purple.

For the $3$-rd test case, one possible plan is to change the color of your $4$-th card to white.

"Constraints"

For all testdata, it is guaranteed that:

• $1 \le T \le 30$;
• $2 \le n \le 10^5$;
• For every positive integer $i$ not exceeding $n$, both $s_i$ and $t_i$ are characters in PVW.

This problem uses bundled tests.

• Subtask 0 (18 points): $n \le 6$.
• Subtask 1 (20 points): $n \le 1000$.
• Subtask 2 (12 points): For every positive integer $i$ not exceeding $n$, $s_i \ne t_i$.
• Subtask 3 (25 points): If you do not perform any operation, then you will not win.
• Subtask 4 (25 points): No special constraints.

Translated by ChatGPT 5