Description

Given two 01-strings $S$ and $T$ of length $n$, you can perform the following operations on string $S$ infinitely many times. In each operation, you may choose one of the following:

• Select two positive integers $l, r$ $(1 \le l \le r \le n)$ and flip the 01 values of $S_l \dots S_r$ (i.e., change 0 to 1 and 1 to 0).

• Select two positive integers $l, r$ $(1 \le l \le r \le n)$ and set all characters in $S_l \dots S_r$ to 0.

• Select two positive integers $l, r$ $(1 \le l \le r \le n)$ and set all characters in $S_l \dots S_r$ to 1.

Your task is to determine the minimum number of operations required to transform $S$ into $T$.

Input Format

The problem uses multiple test cases.

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case:

• The first line contains a 01-string representing $S$.

• The second line contains a 01-string representing $T$.

Output Format

Output $T$ lines, where the $i$-th line contains an integer representing the answer for the $i$-th test case.

3
00000
11111
10101
01010
11100101
11110000 

1
1
2

Hint

【Sample Explanation】

Below is one valid solution for each of the three sample test cases:

• For the first test case, select $l=1, r=5$ and set all characters in $S_l \dots S_r$ to 1.

• For the second test case, select $l=1, r=5$ and flip the 01 values of $S_l \dots S_r$.

• For the third test case, first select $l=4, r=8$ and flip the 01 values of $S_l \dots S_r$, then select $l=5, r=8$ and set all characters in $S_l \dots S_r$ to 0.

【Data Range】

This problem uses bundled tests.

• Subtask 0 (10 points): $n \le 5$.
• Subtask 1 (10 points): $n \le 18$.
• Subtask 2 (30 points): $n \le 2000$.
• Subtask 3 (50 points): No additional constraints.

For all test cases, $1 \le T \le 10$ and $1 \le n \le 5 \times 10^5$.