[old] 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.

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.

Example

Input

3
11101
10110
11101
10010
01100
10110

Output

0
1
2