Alice 和 Bob 正在玩游戏。它们有两个字符串 $$$S$$$ 和 $$$T$$$,长度相同 $$$n$$$,由小写拉丁字母组成。玩家轮流进行,爱丽丝先行。
轮到 Alice 选择从 $$$1$$$ 到 $$$n$$$ 的整数 $$$i$$$、字符串 $$$S$$$ 或 $$$T$$$ 之一以及任何小写拉丁字母 $$$c$$$,并用字符 $$$c$$$ 替换所选字符串中的第 $$$i$$$ 个符号。
轮到 Bob 选择 $$$S$$$ 或 $$$T$$$ 字符串之一,并将其反转。更正式地说,Bob 进行替换 $$$S := \operatorname{rev}(S)$$$ 或 $$$T := \operatorname{rev}(T)$$$,其中 $$$\operatorname{rev}(P) = P_n P_{n-1} \ldots P_1$$$。
游戏持续到字符串 $$$S$$$ 和 $$$T$$$ 相等为止。一旦绳子变得相等,游戏立即结束。
将游戏持续时间定义为游戏期间双方玩家的移动总数。例如,如果 Alice 总共移动了 $$$2$$$,而 Bob 总共移动了 $$$1$$$,则该游戏的持续时间为 $$$3$$$。
Alice 的目标是最小化游戏的持续时间,Bob 的目标是最大化游戏的持续时间。
如果两个玩家都发挥最佳状态,游戏的持续时间是多少?可以证明,游戏将在有限的回合内结束。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$S$$$ 和 $$$T$$$ 的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$S$$$,由小写拉丁字母组成。
每个测试用例的第三行包含一个长度为 $$$n$$$ 的字符串 $$$T$$$,由小写拉丁字母组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在单独的行上输出一个数字 - 所描述游戏的持续时间(如果两个玩家都发挥最佳状态)。
示例
输入 #1
7 5 abcde abxde 5 hello olleo 2 ab cd 7 aaaaaaa abbbbba 1 q q 6 yoyoyo oyoyoy 8 abcdefgh hguedfbh
输出 #1
1 2 3 9 0 2 6
注意
在第一个测试用例中,轮到 Alice 可以用 x 替换字符串 $$$S$$$ 的第三个符号。之后,两个字符串都将变为等于“abxde”,并且游戏将在走一步后结束。由于爱丽丝的目标是用尽可能少的动作完成游戏,因此该动作将是她的最佳第一步之一,最终答案将是 $$$1$$$。
在第二个测试用例中,轮到 Alice 可以用 h 替换字符串 $$$T$$$ 的第五个符号。完成此操作后,$$$S =$$$“hello”,$$$T =$$$“olleh”。然后轮到鲍勃了。轮到他时,他必须反转其中一根弦。如果 Bob 选择字符串 $$$S$$$,那么在轮到他之后,两个字符串都将等于“olleh”,如果他选择字符串 $$$T$$$,那么在轮到他之后,两个字符串都将等于“hello”。因此,在 Alice 提出第一步棋后,游戏肯定会以 $$$2$$$ 步结束。可以证明,Alice 没有任何策略可以在两个玩家都处于最佳状态的情况下以少于 $$$2$$$ 的步数完成游戏。最终答案是$$$2$$$。
在第三个测试用例中,Alice 在第一步中可以用 c 替换字符串 $$$S$$$ 的第二个符号。在此移动之后,$$$S =$$$“ac”,$$$T =$$$“cd”。然后轮到鲍勃了。如果 Bob 反转字符串 $$$S$$$,则在轮到 $$$S =$$$ "ca" 后,$$$T =$$$ "cd"。那么很容易看出,在这种情况下,Alice 肯定可以在 $$$3$$$-rd 步上完成游戏,方法是用 a 替换字符串 $$$T$$$ 的第二个符号,之后两个字符串都将变为等于“ca”。如果 Bob 反转字符串 $$$T$$$,则在轮到 $$$S =$$$ "ac" 后,$$$T =$$$ "dc"。在这种情况下,Alice 也可以通过用 d 替换字符串 $$$S$$$ 的第一个符号,在 $$$3$$$rd 步上确定完成游戏,之后两个字符串都将变为等于“dc”。因此,无论 Bob 的步数如何,Alice 都可以在 $$$3$$$ 步内完成游戏。可以证明,在双方玩家都处于最佳状态的情况下,游戏不能以少于 $$$3$$$ 的步数结束。
在第五个测试用例中,字符串 $$$S$$$ 和 $$$T$$$ 相等,因此游戏将在 $$$0$$$ 移动中结束而不开始。