Photo Matching

You’ll be given two matrix M1 and M2 and another integer K. The size of both M1 and M2 are N*N and each of their cells contains either 0 or 1. You have to find in how many ways you can select a sub-matrix S1 from M1 and another sub-matrix S2 from M2 (both of size K*K) such that they look exactly same.

Input

The first line of the input contains an integer T which denotes the number of test cases.
The first line of each test case contains two integers N and K. The following 2*N lines of a test case represents the matrices. The first N lines contain the cells of matrix M1 and the next N lines contain the cells of matrix M2. See the sample test cases for more details about the format.

Constraints

• 1 ≤ T ≤ 2
• 1 ≤ N ≤ 3000
• 1 ≤ K ≤ 4
• Each cell of the matrices is either 0 or 1

Output

For each test case, print the result in the format “Case X: Y” where Y is the answer to the problem.

Sample

2
3 2
101
111
010
001
111
011
5 2
01001
11100
11011
01101
10001
01001
11100
11001
00101
10011

Case 1: 2
Case 2: 16