CF1834C.Game with Reversing

Alice and Bob are playing a game. They have two strings $S$ and $T$ of the same length $n$ consisting of lowercase latin letters. Players take turns alternately, with Alice going first.

On her turn, Alice chooses an integer $i$ from $1$ to $n$, one of the strings $S$ or $T$, and any lowercase latin letter $c$, and replaces the $i$-th symbol in the chosen string with the character $c$.

On his turn, Bob chooses one of the strings $S$ or $T$, and reverses it. More formally, Bob makes the replacement $S := \operatorname{rev}(S)$ or $T := \operatorname{rev}(T)$, where $\operatorname{rev}(P) = P_n P_{n-1} \ldots P_1$.

The game lasts until the strings $S$ and $T$ are equal. As soon as the strings become equal, the game ends instantly.

Define the duration of the game as the total number of moves made by both players during the game. For example, if Alice made $2$ moves in total, and Bob made $1$ move, then the duration of this game is $3$.

Alice's goal is to minimize the duration of the game, and Bob's goal is to maximize the duration of the game.

What will be the duration of the game, if both players play optimally? It can be shown that the game will end in a finite number of turns.

爱丽丝和鲍勃正在玩一个游戏。他们有两个长度均为 $n$ 的字符串 $S$ 和 $T$，均由小写拉丁字母组成。双方轮流进行操作，爱丽丝先行。

在爱丽丝的回合中，她选择一个整数 $i$（取值范围为 $1$ 到 $n$）、字符串 $S$ 或 $T$ 中的一个，以及任意一个小写拉丁字母 $c$，并将所选字符串中第 $i$ 个位置的字符替换为 $c$。

在鲍勃的回合中，他选择字符串 $S$ 或 $T$ 中的一个，并将其反转。更准确地说，鲍勃执行替换操作 $S := \operatorname{rev}(S)$ 或 $T := \operatorname{rev}(T)$，其中 $\operatorname{rev}(P) = P_n P_{n-1} \ldots P_1$。

游戏持续进行，直到字符串 $S$ 和 $T$ 相等为止。一旦两字符串相等，游戏立即结束。

定义游戏的持续时间为游戏过程中双方所做操作的总次数。例如，若爱丽丝共进行了 $2$ 次操作，而鲍勃共进行了 $1$ 次操作，则该游戏的持续时间为 $3$。

爱丽丝的目标是使游戏持续时间尽可能短，而鲍勃的目标是使游戏持续时间尽可能长。

若双方均采取最优策略，游戏的持续时间是多少？可以证明，该游戏必将在有限步内结束。

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 a single integer $n$ ($1 \le n \le 10^5$) — the length of the strings $S$ and $T$.

The second line of each test case contains a string $S$ of length $n$ consisting of lowercase latin letters.

The third line of each test case contains a string $T$ of length $n$ consisting of lowercase latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 字符串 $S$ 和 $T$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $S$，由小写拉丁字母组成。

每个测试用例的第三行包含一个长度为 $n$ 的字符串 $T$，由小写拉丁字母组成。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, output a single number on a separate line — the duration of the described game, if both players play optimally.

对于每个测试用例，在单独一行输出一个数字——即在双方均采取最优策略的情况下，所描述游戏的持续时间。

In the first test case, in her turn, Alice can replace the third symbol of the string $S$ with x. After that, both strings will become equal to "abxde" and the game will end after one move. Since Alice's goal is to finish the game in as few moves as possible, this move will be one of her optimal first moves, and the final answer will be $1$.

In the second test case, in her turn, Alice can replace the fifth symbol of the string $T$ with h. After this move, $S =$ "hello", $T =$ "olleh". Then Bob makes his turn. In his turn, he must reverse one of the strings. If Bob chooses the string $S$, then after his turn both strings will be equal to "olleh", and if he chooses the string $T$, then after his turn both strings will be equal to "hello". Thus, after the presented first move of Alice, the game will definitely end in $2$ moves. It can be shown that there is no strategy for Alice to finish the game in less than $2$ moves, with both players playing optimally. The final answer is $2$.

In the third test case, in her first move, Alice can replace the second symbol of the string $S$ with c. After this move, $S =$ "ac", $T =$ "cd". Then Bob makes his turn. If Bob reverses the string $S$, then after his turn $S =$ "ca", $T =$ "cd". Then it is easy to see that in this case Alice can definitely finish the game on the $3$-rd move, by replacing the second symbol of the string $T$ with a, after which both strings will become equal to "ca". If Bob reverses the string $T$, then after his turn $S =$ "ac", $T =$ "dc". In this case, Alice can also definitely finish the game on the $3$rd move, by replacing the first symbol of the string $S$ with d, after which both strings will become equal to "dc". Thus, Alice can definitely finish the game in $3$ moves regardless of Bob's moves. It can be shown that the game cannot end in less than $3$ moves, with both players playing optimally.

In the fifth test case, the strings $S$ and $T$ are equal, so the game will end without starting, in $0$ moves.

在第一个测试用例中，轮到 Alice 时，她可以将字符串 $S$ 的第三个字符替换为 x。此后，两个字符串都将变为 "abxde"，游戏将在一步后结束。由于 Alice 的目标是以尽可能少的步数结束游戏，因此该操作是她的最优首步之一，最终答案为 $1$。

在第二个测试用例中，轮到 Alice 时，她可以将字符串 $T$ 的第五个字符替换为 h。此操作之后，$S =$ "hello"，$T =$ "olleh"。接着轮到 Bob 行动。他必须反转其中一个字符串：若 Bob 选择反转字符串 $S$，则其行动后两个字符串均变为 "olleh"；若他选择反转字符串 $T$，则其行动后两个字符串均变为 "hello"。因此，在 Alice 执行上述首步后，游戏必定在 $2$ 步内结束。可以证明：当双方均采取最优策略时，Alice 不存在能在少于 $2$ 步内结束游戏的策略。最终答案为 $2$。

在第三个测试用例中，Alice 在第一步可将字符串 $S$ 的第二个字符替换为 c。此操作之后，$S =$ "ac"，$T =$ "cd"。接着轮到 Bob 行动。若 Bob 反转字符串 $S$，则其行动后 $S =$ "ca"，$T =$ "cd"；此时显然 Alice 可在第 $3$ 步通过将字符串 $T$ 的第二个字符替换为 a 来结束游戏，使两字符串均变为 "ca"。若 Bob 反转字符串 $T$，则其行动后 $S =$ "ac"，$T =$ "dc"；此时 Alice 同样可在第 $3$ 步通过将字符串 $S$ 的第一个字符替换为 d 来结束游戏，使两字符串均变为 "dc"。因此，无论 Bob 如何行动，Alice 都能确保在 $3$ 步内结束游戏。可以证明：当双方均采取最优策略时，游戏无法在少于 $3$ 步内结束。

在第五个测试用例中，字符串 $S$ 与 $T$ 相等，因此游戏无需开始即已结束，共 $0$ 步。