题目描述

你和她正在进行一个游戏。

你和她各有 $n$ 张有序的卡牌，每张卡牌的颜色可能为粉色、紫色或白色。

从她开始，你和她需要各自按照卡牌的顺序，轮流打出手里的卡牌。打出的卡牌将会被移至牌堆中。

若某个人打出卡牌后，牌堆中三种颜色的卡牌的数量相同，则这个人获胜，游戏结束。若你和她的卡牌都打完后，还没有人获胜，则游戏平局。

在游戏开始前，你可以进行若干次操作。每次操作，你可以给任意一个人的任意一张卡牌更换颜色。

你想求出，你至少需要进行多少次操作才能使她获胜。可以证明，一定存在至少一种可以使她获胜的操作方案。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据：

• 第一行一个正整数 $n$。
• 第二行一个长度为 $n$ 的字符串 $s$，描述她的卡牌：
  • 若 $s_i$ 为 P，则表示她的第 $i$ 张卡牌的颜色为粉色；
  • 若 $s_i$ 为 V，则表示她的第 $i$ 张卡牌的颜色为紫色；
  • 若 $s_i$ 为 W，则表示她的第 $i$ 张卡牌的颜色为白色。
• 第三行一个长度为 $n$ 的字符串 $t$，描述你的卡牌：
  • 若 $t_i$ 为 P，则表示你的第 $i$ 张卡牌的颜色为粉色；
  • 若 $t_i$ 为 V，则表示你的第 $i$ 张卡牌的颜色为紫色；
  • 若 $t_i$ 为 W，则表示你的第 $i$ 张卡牌的颜色为白色。

其中，$s_i$ 表示字符串 $s$ 的第 $i$ 个字符，$t_i$ 同理。

输出格式

对于每组测试数据，输出一行一个整数，表示你使她获胜所至少需要进行的操作的次数。若你不需要进行操作就能使她获胜，则你需要输出 $0$。

可以证明，一定存在至少一种可以使她获胜的操作方案。

3
2
PW
VP
5
PPWWP
PWVWV
6
WVPPWW
VVPVWP

0
2
1

提示

「样例解释 #1」

对于第 $1$ 组测试数据，不需要进行操作就能使她获胜。

对于第 $2$ 组测试数据，一种可能的操作方案为将她的第 $4$ 张卡牌和第 $5$ 张卡牌的颜色均更换为紫色。

对于第 $3$ 组测试数据，一种可能的操作方案为将你的第 $4$ 张卡牌的颜色更换为白色。

「数据范围」

对于所有测试数据，保证：

• $1 \le T \le 30$；
• $2 \le n \le 10^5$；
• 对于所有不大于 $n$ 的正整数 $i$，满足 $s_i$ 和 $t_i$ 均为 PVW 中的某个字符。

本题采用捆绑测试。

• Subtask 0（18 points）：$n \le 6$。
• Subtask 1（20 points）：$n \le 1000$。
• Subtask 2（12 points）：对于任意不大于 $n$ 的正整数 $i$，都满足 $s_i \ne t_i$。
• Subtask 3（25 points）：若你不进行任何操作，则你不会获胜。
• Subtask 4（25 points）：无特殊限制。