L. Plantations
time limit per test
3 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You're given a matrix with N lines and N columns. Let's define sum of a square submatrix as sum of all numbers from its main diagonal and from its secondary diagonal. Note that the intersection of the diagonals needs to be added only once to the sum. For example, for the matrix

1 2 3

4 5 6

7 8 9

the sum is 1+5+9+7+3 = 25.

Find the largest square submatrix such as its sum is smaller or equal to W.

Input

The first line contains T, the number of tests (T ≤ 20). Next T lines describe the test cases. On first line of each test there are given two numbers N and W (1 ≤ N ≤ 1000, W is a 32-bit number (can be stored in int type)).

Next N lines contain N elements, describing the element of the matrix. All numbers are positive, up to int maximum value.

Output

Outout the answer for each of the T test cases

Examples
Input
1
3 5
1 1 1
1 1 1
1 1 1
Output
3
Note

Note: The time limit of this problem is unusual. Please check it.