As an experienced boomerangist, you take great pride in your trusty boomerang, and you'd like to be able to show it off! Unfortunately, it doesn't look quite right yet...
Like all boomerangs, yours is symmetrical in shape, with two N millimetre-long halves. However, what's not necessarily symmetrical is its paint job — each millimetre-long section of each half has been painted some color. There are 26 possible colors, represented by uppercase letters ("A" to "Z"), and the ith section of the left half (counting from the left end) has color Ai, while the ith section of the right half (counting from the right end) has color Bi. You'd like your boomerang to be completely symmetrical (which is the case when the ith section in the left half has the same color as the ith section in the right half, for all 1 ≤ i ≤ N) as soon as possible!
To that end, you're enlisting the help of your two best friends, Jack and Jill, to repaint the left half of your boomerang until it matches the right half. Every second, Jack may paint over a "prefix" of the left half with a solid color, while Jill may simultaneously paint over a disjoint "suffix". In other words, every second, Jack and Jill will each select a color (from "A" to "Z"), Jack will select a value x (0 ≤ x ≤ N), and Jill will select a value y (0 ≤ y ≤ N - x). Then, Jack will repaint the first x sections of the left half of the boomerang with his color, while Jill will repaint the last y sections of the left half of the boomerang with her color. Painting over a section completely overwrites its previous color.
What's the minimum amount of time (in seconds) it can take Jack and Jill to make your boomerang completely symmetrical?
Input
Input begins with an integer T, the number of boomerangs you want to decorate. For each boomerang, there is first a line containing the integer N, then two lines that each contain a string of length N. The ith character of the second line is Ai. The ith character of the third line is Bi.
Output
For the ith boomerang, print a line containing "Case #i: " followed by the minimum number of seconds it will take Jack and Jill to make your boomerang's paint job symmetrical.
Constraints
1 ≤ T ≤ 75
1 ≤ N ≤ 100,000
Explanation of Sample
The first boomerang is already symmetrical, so no work needs to be done. The second boomerang can be made symmetrical in 1 second. Jack will cover the first millimetre with 'C', and Jill will cover the third millimetre with 'A'. The third boomerang takes 2 seconds to paint. One possible solution is for Jack to paint the first two millimetres with 'A' and then the first millimetre with 'B'.
Sample input
Code: Select all
5
3
ABC
ABC
3
ABC
CBA
3
ABC
BAC
9
FOXENRULE
NOREAALLY
19
DOYOULIKEBOOMERANGS
OOBOOOOVVBOOEAAAGGSCode: Select all
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 3
Case #5: 4