「CROI · R2」01-string

给定两个长度为 $n$ 的 $01$ 串 $S,T$，你可以对串 $S$ 执行无限次操作，每次都可以从以下操作中任选一个执行： - 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r \ 01$ 反转。 - 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r $ 全部改为 $0$。 - 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r $ 全部改为 $1$。 你需要回答最少使用几次操作才能把 $S$ 变成 $T$。

**本题采用多组数据测试。** 第一行一个正整数 $T$，表示数据组数。 对于每组数据： 第一行一个 $01$ 串，表示串 $S$。 第二行一个 $01$ 串，表示串 $T$。

一共 $T$ 行，第 $i$ 行一个整数，表示第 $i$ 组数据的答案。

3
00000
11111
10101
01010
11100101
11110000 

1
1
2

**【样例解释】** 以下提供样例三组数据的合法方案之一： 对于第一组数据，选取 $l=1,r=5$，将 $S_l\dots S_r$ 全部变成 $1$。 对于第二组数据，选取 $l=1,r=5$，将 $S_l\dots S_r \ 01$ 反转。 对于第三组数据，先选取 $l=4,r=8$，将 $S_l\dots S_r$ $01$ 反转，再选取 $l=5,r=8$，将 $S_l\dots S_r$ 全部变成 $0$。 **【数据范围】** **本题采用捆绑测试**。 - Sub 0（10 points）：$n\le 5$。 - Sub 1（10 points）：$n\le 18$。 - Sub 2（30 points）：$n\le 2000$。 - Sub 3（50 points）：无特殊限制。 对于所有的数据，$1\le T \le 10$，$1\le n\le 5\times 10^5$。