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.
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.
For each test case, print the result in the format “Case X: Y” where Y is the answer to the problem.
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