CF2181M.Medical Parity

Nurse Mira works in an allergy clinic. For each patient Mira tests $n$ allergens in a fixed order. The outcome of the tests is written down as a binary string $x$ of length $n$: for each allergen, 1 means a positive reaction and 0 means no reaction.

To analyze how the reactions are distributed, Mira also writes a parity control string for $x$. For a binary string $x$ of length $n$, the parity control string $y$ is defined as follows. For every position $i$ ($1 \le i \le n$), let $c_i$ be the number of characters equal to 1 among the first $i$ characters of $x$ (including position $i$). The parity control string $y$ is the binary string of length $n$ such that $y_i = c_i \mod 2$ for all $i$ ($1 \le i \le n$). In other words, $y_i$ is 1 if $c_i$ is odd and 0 if $c_i$ is even. For example, if $x = 11101$, then $y = 10110$.

Unfortunately, when recording the data, some bits in the test result string and the parity control string may have been written incorrectly. For a given patient, Mira later finds in the system two binary strings $x'$ and $y'$ of the same length $n$. They were intended to be some true test result string $x$ and its parity control string $y$, but some bits in $x$ and $y$ might have been flipped during recording. For instance, in the previous example only the 3rd bit in $y$ could have been flipped, resulting in $x' = 11101$ and $y' = 10010$.

In one bit flip, a position in one of the two strings is chosen and the bit at this position is flipped (changing 0 to 1 or 1 to 0). Mira wants to know the minimal number of bit flips that could have happened when recording the data.

Formally, you are given two binary strings $x'$ and $y'$ of length $n$. You want to obtain two strings $x$ and $y$ of length $n$ from $x'$ and $y'$ by flipping some bits in $x'$ and $y'$, so that $y$ is a parity control string of $x$. Find the minimal possible total number of bit flips needed.

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

为了分析反应的分布情况，米拉还为 $x$ 记录了一个奇偶校验控制串（parity control string）。对于长度为 $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 \bmod 2$。换言之，若 $c_i$ 为奇数，则 $y_i = 1$；若 $c_i$ 为偶数，则 $y_i = 0$。例如，若 $x = 11101$，则 $y = 10110$。

不幸的是，在录入数据时，测试结果串和奇偶校验控制串中可能有若干比特被错误记录。对于某位患者，米拉后来在系统中发现两个等长为 $n$ 的二进制字符串 $x'$ 和 $y'$。它们本应分别是某个真实测试结果串 $x$ 及其对应的奇偶校验控制串 $y$，但在录入过程中 $x$ 和 $y$ 中的部分比特可能被翻转（即 0 变 1 或 1 变 0）。例如，在前述例子中，仅 $y$ 的第 3 位被翻转，就会导致 $x' = 11101$、$y' = 10010$。

一次比特翻转操作指：在 $x'$ 或 $y'$ 中任选一个位置，并将该位置上的比特翻转（0 变 1 或 1 变 0）。米拉希望知道录入数据时可能发生的最少比特翻转次数。

形式化地，给定两个长度为 $n$ 的二进制字符串 $x'$ 和 $y'$，你需要通过对 $x'$ 和 $y'$ 进行若干比特翻转，得到两个长度为 $n$ 的字符串 $x$ 和 $y$，使得 $y$ 是 $x$ 的奇偶校验控制串。求所需的最少总翻转次数。

The first line of the input contains the number of test cases $t$. The $2t$ lines follow — two lines for each test case. The first line of each test case contains a non-empty binary string $x'$ consisting of characters 0 and 1. The second line contains a binary string $y'$ consisting of characters 0 and 1 with the same length as $x'$.

The total length of all $x'$ strings in the input does not exceed $10^6$.

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

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

Print $t$ lines — one line for each test case. For each test case, print a single integer — the minimal possible number of bit flips that could have happened when recording the data.

输出 $t$ 行——每行对应一个测试用例。对于每个测试用例，输出一个整数——记录数据过程中可能发生的最少比特翻转次数。