#1578 Max K Trace

32  10 s   128 MB  

Description

The digit in element i chracter j of mat will correspond to the value in row i column j of an N x N matrix.
Choosing k rows and k columns determines a k x k submatrix of mat.
To compute the trace of such a submatrix S, first extract S from mat and reindex the rows and columns maintaining the original order. Add together all values along the main diagonal of the reindexed matrix (values with the same reindexed row and column).
Find the largest trace considering all possible k x k submatrices.

Input

The first line of the input gives a number of test cases, T. Each test case consists of an integer n and n by n digits.
The first line of each test cases contains two positive integer N(1<=N<=50), the size of the mat and K(1<=K<=N), size of submatrix.
The following N lines contain exactly N character per line and describe elements of mat. j-th Character in i-th row of mat denotes a element, mati,j.

Output

For each test case, write a answer in single line.

Sample Input

Sample Output

4
3 3
123
456
789
2 1
12
93
5 3
12689
55555
55555
55555
55555
15 5
494599520389852
303896953907791
287493604901139
149554299340006
893640109028429
564962730433253
075854577852319
453201529585621
950489162577436
630040569640126
415141646262027
837673828874883
785041862021729
850806584119109
217671590991247
15
9
16
45