题目描述

护士米拉在过敏诊所工作。对于每位病人，米拉会按固定顺序检测 $n$ 种过敏原。检测结果被记录为一个长度为 $n$ 的二进制串 $x$：每一位代表一种过敏原，1 代表阳性反应，0 代表无反应。

为了分析反应分布，米拉还会为 $x$ 写出一条奇偶校验串 $y$。对于长度为 $n$ 的二进制串 $x$，奇偶校验串 $y$ 的定义如下： 对每个位置 $i$（$1 \le i \le n$），令 $c_i$ 为 $x$ 的前 $i$ 个字符中 1 的个数（包含第 $i$ 位）。奇偶校验串 $y$ 是长度为 $n$ 的二进制串，满足 $y_i = c_i \bmod 2$。换句话说，如果 $c_i$ 是奇数则 $y_i=1$，偶数则 $y_i=0$。 例如，若 $x = 11101$，则 $y = 10110$。

不幸的是，在记录数据时，检测串和校验串里的一些比特可能被写错了。对于某个病人，米拉在系统里找到两个等长的二进制串 $x'$ 和 $y'$，它们原本应该是真实检测串 $x$ 和它对应的奇偶校验串 $y$，但记录过程中部分比特发生翻转。 比如上一个例子中，仅翻转 $y$ 的第 3 位，就得到 $x' = 11101$，$y' = 10010$。

一次比特翻转操作：选择其中一个串的某一个位置，把该位 0 变 1 或 1 变 0。米拉想知道记录过程最少发生了多少次比特翻转。

形式化地：给定两个长度为 $n$ 的二进制串 $x'$、$y'$，你可以翻转 $x'$ 和 $y'$ 中的若干比特得到 $x,y$，要求 $y$ 是 $x$ 的奇偶校验串。求总翻转次数的最小值。

输入格式

第一行一个整数 $t$，代表测试用例数量。 接下来 $2t$ 行，每组测试用例占两行： 第一行是一个非空二进制串 $x'$，仅由 0、1 组成； 第二行是和 $x'$ 长度相同的二进制串 $y'$。

输入中所有 $x'$ 的总长度不超过 $10^6$。

输出格式

一共输出 $t$ 行，每组测试用例输出一行一个整数：最小翻转次数。

3
11101
10110
11101
10010
01100
10110

0
1
2

原题链接

原题链接