保险箱的密码 【大红】

Description:

最近sed同学设计了一套保险箱密码锁，密码锁上有依次排好的0、1数字键，保险箱密码是由0和1组成的数字串。开启这个保险箱需要正确的密码，还需要将密码锁上数字键设定为对应的0或1，而这个过程需要特定的技巧：每次变换的工作：将密码锁上连续的0、1数字串用同样数目的全0或全1数字串代替。现给你正确的密码 (不超过200），请计算开启这个保险箱，最少需要经过多少次变换。

Input:

第一行是一个正整数：测试用例数目，最多为100。之后，每个测试用例包括两行：

l       第1行给出密码锁上初始的0、1数字串(不超过200）

l       第2行给出保险箱的正确密码

Output:

对于每个测试用例:

l       开启保险箱需要的最少变换数

Sample Input:

2
000
111
1011
0010

Sample Output:

1
2

Note:

本题由旧版NOJ导入，来源：“IBM南邮杯”团队赛2009