Limits 4s, 1.0 GB

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

InputOutput
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

Submit

Login to submit.

Contributors

Statistics

73% Solution Ratio
fsshakkhorEarliest, Apr '20
Kuddus.6068Fastest, 0.3s
vipghn2003Lightest, 10 MB
shelby70Shortest, 861B
Toph uses cookies. By continuing you agree to our Cookie Policy.