题目描述

给定两个长度为 $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$。