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.

Input

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$$$.

Output

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.

Medical Parity

Examples