题解

题面描述

给定一个长度为 $n$ 的 $01$ 串 $x$（下标从 $1$ 到 $n$），和另一个长度为 $n-1$ 的 $01$ 串 $y$（下标从 $1$ 到 $n-1$）。串 $y$ 用于约束串 $x$，具体规则如下：

• 如果 $y_i=1$（$1 \leq i \leq n-1$），则要求 $x_i \neq x_{i+1}$。
• 如果 $y_i=0$（$1 \leq i \leq n-1$），则要求 $x_i = x_{i+1}$。

初始的串 $x$ 可能不满足 $y$ 的要求，允许通过将 $x$ 中的某个字符取反（即执行 $x_i := x_i \oplus 1$）来修改。目标是修改尽可能少的字符，使得最终的 $x$ 串满足所有的约束条件。

题目内容

小苯有一个长度为 $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⊕1$。(其中 ⊕ 表示按位异或运算。)

输入描述

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

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

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

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

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

输出描述

对于每组测试数据:

在单独的一行输出一个整数，表示最少的修改次数，

样例1

输入

2
8
11001011
1000111
6
101010
11111

输出

4
0

说明

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

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