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
for num in range(input()):
	# n  =input()
	p,q = map(int,raw_input().split())
	arr1 = list(raw_input())
	arr2 = list(raw_input())
	dp=[[0 for i in range(q+1)] for i in range(p+1)]
	for i in range(1,p+1):
		for j in range(1,q+1):
			if arr1[i-1]==arr2[j-1]:
				dp[i][j] += (1+ dp[i-1][j-1])
			else:
				dp[i][j] += max(dp[i-1][j],dp[i][j-1])
	ans = p+q-dp[p][q]
	
	print "Case "+str(num+1)+": "+str(ans)