Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are given two binary strings $A$ and $B$ with the same length.

You may perform the following operation any number of times (including zero): pick a substring of $A$ with odd length and invert all the bits (change '0' to '1' or vice versa) at odd positions in this substring. For example, if we choose a substring "01011", we can convert it to "11110" (bits at odd positions are bold).

Determine the minimum number of operations required to change the string $A$ to the string $B$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single string $A$.
The second line contains a single string $B$.

------ Output ------
For each test case, print a single line containing one integer — the minimum number of operations required.

------ Constraints ------
$1 ≤ T ≤ 10^{3}$
$1 ≤ |A| = |B| ≤ 10^{5}$
$A$ and $B$ contain only characters '0' and '1'
the sum of $|A|$ over all test cases does not exceed $10^{5}$

----- Sample Input 1 ------
3

100001

110111

1010

1010

000

111
----- Sample Output 1 ------
2

0

2
----- explanation 1 ------
Example case 1: Initially, $A$ is "100001". We choose the substring "000" between the $2$-nd and $4$-th character and convert it to "101".

Now $A$ becomes "110101". We choose the string "0" containing only the $5$-th character and convert it to "1".

Finally, $A$ becomes "110111", which is equal to $B$.

Example case 2: $A$ and $B$ are initially equal, so there is no need to perform any operation.

见题面

见题面