Apocalyptic Alignment#300
Apples and bananas are tasty, but also dangerous. An ancient prophecy says that if you arrange them in a certain order, the world will face disaster! One cloudy day, tired of this world, you decide to test this prophecy.
In front of you lies a line of apples and bananas. Only one operation is allowed: at each step, you may choose any number of consecutive fruits and replace them with the same number of fruits of one type. Your task is to find the minimum number of operations needed to achieve the goal.
The first line contains the number of test cases (t \leq 100). Each test case consists of two lines: the first line contains the initial arrangement of fruits, and the second line contains the arrangement that leads to disaster. Both lines contain only two letters: A (for apple) and B (for banana). Both lines have equal length, not exceeding . No line contains leading or trailing spaces.
For each test case, output the minimum number of operations needed to reach the desired arrangement, on a separate line.
Example 1