Problem Description

你有两个无限长$01$串$S, T$，分别记作$S_0S_1\dots$和$T_0T_1\dots$。其中$S$和$T$从$n$位之后都是$0$，也就是当$i\geq n$，有$S_i=T_i=0$。

你可以对$S$串进行操作：

- 修改$S$串的某一位，从$0$变成$1$或者从$1$变成$0$。
- 将$S$当成二进制数加$1$，也就是记$s=\sum_{i\geq 0} S_i2^i$，将$S$变成$s+1$二进制表示的形式，其中低位在最前面。

问最少的步数将$S$变成$T$。

Input

第一行一个正整数$T(1\leq T\leq 10^4)$表示数据组数。

对于每组数据，第一行一个整数$n$，接下来两行长度为$n(1\leq n\leq 10^5)$的$01$串$S$和$T$，表示$S$和$T$的前$n$位。

保证$\sum n\leq 10^6$。

Output

对于每组数据，输出一个整数，表示步数。

3
5
11111
00000
5
10100
01010
5
00000
00001

2
3
1

Hint

第一组数据中，可以选择先加一变成 "000001"，然后将S₅变成 '0'。

第二组数据中，先加一变为 "01100"，然后直接修改。

第三组数据中，直接修改。