米拉护士在过敏诊所工作。对于每位患者,Mira 按固定顺序测试 $$$n$$$ 过敏原。测试结果被写成长度为 $$$n$$$ 的二进制字符串 $$$x$$$:对于每种过敏原,1 表示阳性反应,0 表示无反应。
为了分析反应如何分布,Mira 还写了一个 奇偶校验控制字符串 为 $$$x$$$。对于长度为$$$n$$$的二进制字符串$$$x$$$,奇偶校验控制字符串$$$y$$$定义如下。对于每个位置 $$$i$$$ ($$$1 \le i \le n$$$),令 $$$c_i$$$ 为 $$$x$$$ 的前 $$$i$$$ 个字符中等于 1 的字符数(包括位置 $$$i$$$)。奇偶校验控制字符串 $$$y$$$ 是长度为 $$$n$$$ 的二进制字符串,对于所有 $$$i$$$ ($$$1 \le i \le n$$$),$$$y_i = c_i \mod 2$$$ ($$$1 \le i \le n$$$)。换句话说,如果 $$$c_i$$$ 为奇数,则 $$$y_i$$$ 为 1;如果 $$$c_i$$$ 为偶数,则 $$$c_i$$$ 为 0。例如,如果 $$$x = 11101$$$,则 $$$y = 10110$$$。
不幸的是,在记录数据时,测试结果字符串和奇偶校验控制字符串中的某些位可能被错误地写入。对于给定的患者,Mira 随后在系统中找到了两个长度相同的二进制字符串 $$$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$$$ 行——每个测试用例两行。每个测试用例的第一行包含一个由字符 0 和 1 组成的非空二进制字符串 $$$x'$$$。第二行包含一个由字符 0 和 1 组成的二进制字符串 $$$y'$$$,其长度与 $$$x'$$$ 相同。
输入中所有 $$$x'$$$ 字符串的总长度不超过 $$$10^6$$$。
输出
打印 $$$t$$$ 行 — 每个测试用例一行。对于每个测试用例,打印一个整数 - 记录数据时可能发生的最小可能数量的位翻转。
示例
输入复制
3111011011011101100100110010110
输出复制
012