题面描述

小苯有一个长度为 $n$ 的 $01$ 串 $x$（下标从 $1$ 到 $n$），格格有一个长度恰好为 $n-1$ 的 $01$ 串 $y$（下标从 $1$ 到 $n-1$）。要求在修改尽可能少的 $x$ 串字符后，使其满足以下匹配规则：

• 若 $y_i = 1$，则必须有 $x_i \neq x_{i+1}$；
• 若 $y_i = 0$，则必须有 $x_i = x_{i+1}$。

一次修改操作是选择一个位置 $i\,(1\le i\le n)$，令 $x_i := x_i \oplus 1$。求最少需要多少次修改才能使匹配成立。

问题本质分析

题目内容

小苯有一个长度为$n$的$01$串$x$(下标从$1$到$n$)，巧合的是格格也有一个长度恰好为$n-1$的$01$串$y$。(下标从$1$到$n-1$)

据说，格格的字符串$y$是用来匹配小苯的字符串$x$的，具体来说:

如果$y_i=1(1≤i≤n-1)$，则意味着必须有:$x_i≠x_i+1$。

如果$y_i=0(1≤i≤n-1)$,则意味着必须有:$x_i=x_i+1$。

而现在小苯的串$x$并不一定满足$y$串的匹配要求，因此格格希望小苯修改尽可能少的字符，使得匹配成立，请你帮小苯算一算至少需要修改多少个字符吧。

修改:选择$i(1≤i≤n)$,执行:$x_i:=x_i\oplus1$(其中$\oplus$表示按位异或运算。)

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦100)$代表数据组数，每组测试数据描述如下:

第一行输入一个正整数 $n(2≦n≤10^6)$代表串的长度。

第二行输入一个长度为$n$，仅由字符‘$0$’和'$1$'构成的字符串$x$。

第三行输入一个长度为$n-1$，仅由字符'$0$'和'$1$'构成的字符串$y$

除此之外，保证单个测试文件的n之和不超过$10^6$

输出描述

对于每组测试数据: 在单独的一行输出一个整数，表示最少的修改次数。

样例1

输入

2
8
11001011
1000111
6
101010
1111

输出

4
0

说明

对于第一组测试数据，我们修改串为:“$10000101$”即可,需要至少$4$次修改操作。

对于第二组测试数据,我们不需要修改,因非输出$0$即可。