A DNA sequence can be represented by a string of letters T, A, C, and G representing four different amino acids. DNA sequences are often matched to infer structural or functional similarities between living beings. Given two DNA sequences X and Y, the sequence Y is said to be contained in X if Y can be obtained from X by deleting 0 or more letters (not necessarily consecutive) in X.
Given two DNA sequences X and Y, what can be the minimum length of a third sequence Z such that both X and Y are contained in Z?

Input
The first line contains the number of test cases N (0 < N ≤ 3). For each test case, the first line contains two integers P and Q (0 < P, Q ≤ 1000) denoting the number of letters in the two sequences X and Y respectively. The second line contains the sequence X and the third line contains the sequence Y.

Output
For each test case, print the case number, followed by a colon, followed by a single space, followed by a single integer indicating the minimum length of sequence Z.

Sample Input

2
7 6
TAGCTAG
ATCATG
10 9
GGATGCTACA
TCTACCGTA

Sample Output

Case 1: 9
Case 2: 13

见题面

见题面