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

为了分析反应的分布情况，Mira 还为 $x$ 写了一个奇偶校验字符串 $y$。对于长度为 $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$。

不幸的是，在记录数据时，测试结果字符串和奇偶校验字符串中的某些位可能被错误地记录了。对于给定的患者，Mira 后来在系统中发现了两个长度相同为 $n$ 的二进制字符串 $x'$ 和 $y'$。它们原本应该是某个真实的测试结果字符串 $x$ 及其奇偶校验字符串 $y$，但在记录过程中，$x$ 和 $y$ 中的某些位可能被翻转了。例如，在前面的例子中，可能只有 $y$ 中的第 3 位被翻转了，导致 $x' = 11101$ 且 $y' = 10010$。

在一次位翻转中，选择两个字符串之一中的某个位置，并将该位置的位翻转（将 0 变为 1，或将 1 变为 0）。Mira 想知道在记录数据时可能发生的最少位翻转次数。

形式化地，给定两个长度为 $n$ 的二进制字符串 $x'$ 和 $y'$。你想通过翻转 $x'$ 和 $y'$ 中的某些位，从 $x'$ 和 $y'$ 得到两个长度为 $n$ 的字符串 $x$ 和 $y$，使得 $y$ 是 $x$ 的奇偶校验字符串。求所需的最少总位翻转次数。

输入格式

输入的第一行包含测试用例的数量 $t$。接下来的 $2t$ 行——每个测试用例占两行。

每个测试用例的第一行包含一个非空的二进制字符串 $x'$，由字符 0 和 1 组成。

第二行包含一个二进制字符串 $y'$，由字符 0 和 1 组成，其长度与 $x'$ 相同。

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

输出格式

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

样例

输入样例 1

3
11101
10110
11101
10010
01100
10110

输出样例 1

0
1
2