H :: Homework Matching

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Some distances between two strings have been defined as the number of operations should be done to make the sequences equal (for example edit distance in information retrieval). We have defined a new nondeterministic operation as followed: Find a common substring (CS) and replace it in both strings with a new symbol.

A CS is a sequence of characters which has been seen in both strings consecutively. In each operation just one replacement is done in each string even if there are more occurrences of that substring. For example, both "ABAB" and "ABABAB" are CS'es in "ABCABABABB" and "ABBABABABCAB". By replacing "ABAB" with the new symbol Z, in "ABAABABABB", the string can be one of "ABAZABB" or "ABAABZB". Assume there is an infinite set of new symbols which you can use in the replacements. However, each symbol can be used just once.

Due to that this program will be used for plagiarism detection in homeworks; the new symbols should be occurred with the same order in both strings. This progress continues while the size of strings can decrease. Distance of two strings is defined as minimum possible size of the largest string after applying the best operations. For two strings "ABCABABABB" and "ABBABABABCAB", you can replace "ABABAB" by Z₁ to achieve "ABCZ₁B" and "ABBZ₁CAB", respectively. Then by replacing "AB" with Z₂, final strings will be formed as "Z₂CZ₁B" and "Z₂BZ₁CAB", respectively. Distance of these strings is 6.

Input

The number of test-cases is given as T<100 in the first line. In followed 2T lines, T test-cases have been given (two lines per test). In each line of each test-case, one of the associated strings is presented by at most 1000 consecutive characters of ‘A’, ‘B’ or 'C'.

Output

Print the distance of two given strings in a separate line per test-case.

Sample Input

6
ABCABABABB
ABBABABABCAB
ABCABABABB
BABABABCAB
ABABABAB
BABABABA
AAAAABBBBB
BBBBBAAAAA
AAAAABBBBB
ABABABABAB
AACBAC
ABCAA

Sample Output

6
5
2
6
9
5

Submit

Source: 13th Iran Nationwide Internet Contest - Shiraz