P14794 [NERC 2025] Medical Parity

Mira 护士在一家过敏诊所工作。对于每位患者，Mira 按固定顺序测试 $n$ 种过敏原。测试结果被记录为一个长度为 $n$ 的二进制字符串 $x$：对于每种过敏原，1 表示阳性反应，0 表示无反应。 为了分析反应是如何分布的，Mira 还会为 $x$ 编写一个 **奇偶控制字符串**。对于一个长度为 $n$ 的二进制字符串 $x$，奇偶控制字符串 $y$ 定义如下：对于每个位置 $i$ ($1 \le i \le n$)，令 $c_i$ 为 $x$ 的前 $i$ 个字符（包括位置 $i$）中等于 1 的字符个数。奇偶控制字符串 $y$ 是一个长度为 $n$ 的二进制字符串，使得对所有 $i$ ($1 \le i \le n$)，有 $y_i = c_i \mod 2$。换句话说，如果 $c_i$ 为奇数则 $y_i$ 为 1，如果 $c_i$ 为偶数则 $y_i$ 为 0。例如，如果 $x = 11101$，那么 $y = 10110$。 不幸的是，在记录数据时，测试结果字符串和奇偶控制字符串中的某些位可能被错误地书写了。对于一位给定的患者，Mira 后来在系统中找到了两个长度相同、均为 $n$ 的二进制字符串 $x'$ 和 $y'$。它们本应是某个真实的测试结果字符串 $x$ 及其奇偶控制字符串 $y$，但在记录过程中 $x$ 和 $y$ 的一些位可能被翻转了。例如，在前面的例子中，只有 $y$ 的第 3 位可能被翻转了，导致 $x' = 11101$ 和 $y' = 10010$。 在一次 **位翻转** 中，选择两个字符串中某一位置，将该位置的位进行翻转（将 0 变为 1 或将 1 变为 0）。Mira 想知道在记录数据时可能发生的最小位翻转次数。 形式化地说，你被给予两个长度为 $n$ 的二进制字符串 $x'$ 和 $y'$。你希望通过翻转 $x'$ 和 $y'$ 中的一些位，得到两个长度为 $n$ 的字符串 $x$ 和 $y$，使得 $y$ 是 $x$ 的奇偶控制字符串。找出所需的最小可能的总位翻转次数。

输入的第一行包含测试用例的数量 $t$。接下来是 $2t$ 行 —— 每个测试用例两行。每个测试用例的第一行包含一个非空的二进制字符串 $x'$，由字符 0 和 1 组成。第二行包含一个二进制字符串 $y'$，由字符 0 和 1 组成，且长度与 $x'$ 相同。 输入中所有 $x'$ 字符串的总长度不超过 $10^6$。

输出 $t$ 行 —— 每个测试用例一行。对于每个测试用例，输出一个整数 —— 在记录数据时可能发生的最小位翻转次数。

翻译由 DeepSeek V3 完成