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.
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.
For each test case, output a single line containing the minimum number of steps to destroy the world.
2 BB AA BAAAB ABBAA
1 2
Migrated from old NTUJ.
2008 Stanford Local
| No. | Testdata Range | Score |
|---|