P10766 「CROI · R2」01-string

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

**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 $T$ lines, where the $i$-th line contains an integer representing the answer for the $i$-th test case.

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