eolymp
bolt
Try our new interface for solving problems
Problems

Apocalyptic Alignment

Apocalyptic Alignment

Time limit 1 second
Memory limit 122 MiB

Apples and bananas are tasty, but also dangerous. An ancient prophecy said that when you align them in a certain order, the world will be destroyed! On a cloudy day, being tired of this world, you decide to try it out. You started with a line of apples and bananas, and there is one type of allowed operation: At each step, any number of consecutive items in the line can be chosen, replaced by the same amount of fruits of one kind. You can’t wait to destroy the world, so you want to know the minimum number of steps to achieve your goal.

Input The first line of the input file contains a single number t (t <= 100), the number of test cases. Each test case consists of two lines, where the first line indicates the initial pattern, and the second line indicates the evil pattern that can destroy the world. Both lines contain only characters 'A' and 'B', where 'A' stands for an apple and 'B' stands for a banana. The two lines will have the same length (no greater than 200), and there is no leading or trailing white spaces. Output For each test case, output a single line containing the minimum number of steps to destroy the world.

Examples

Input example #1
2
BB
AA
BAAAB
ABBAA
Output example #1
1
2