题目描述

Alice和Bob在玩"反转了"游戏。

游戏规则是这样的:

1. 有两个字符串 $S$ 和 $T$ 。
2. 他们两个轮流进行操作，Alice先手。
3. Alice每次可以将字符串 $S$ 或 $T$ 中的一个字符变成任意一个字符。她的目标是使游戏的步数尽可能小。
4. Bob可以选择 $S$ 或 $T$ 中的一个字符串，然后将其反转。他的目标是使游戏的步数尽可能大。
5. 两个字符串一模一样时游戏结束。

问:在双方都使用最佳策略的情况下，他们一共会走几步(某人的操作完成之后记作一步)。

格式

输入

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

每组数据中,第一行为一个正整数$n$,表示两个字符串的长度，第二行和第三行分别为字符串 $S$ 和 字符串 $L$。

其中，$1 \le T \le 10^3$,$1 \le n \le 10^6$,$\sum n_i \le 10^6$。

输出

对于每组数据输出一个数字。

表示在双方都使用最佳策略的情况下，完成该局游戏的步数。

样例

7
5
abcde
abxde
5
hello
olleo
2
ab
cd
7
aaaaaaa
abbbbba
1
q
q
6
yoyoyo
oyoyoy
8
abcdefgh
hguedfbh

1
2
3
9
0
2
6