#include <bits/stdc++.h>

using namespace std;

ifstream in("plantatii.in");
ofstream out("plantatii.out");

int mat[1002][1002];
int r[1002][1002];
int l[1002][1002];

int main()
{
	int t;
	in>>t;
	while(t--)
	{
		int n,w;
		in>>n>>w;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				in>>mat[i][j];
				r[i][j]=r[i-1][j-1]+mat[i][j];
				l[i][j]=l[i-1][j+1]+mat[i][j];
			}
		long long ans=0;
		long long s=0;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				for(int k=ans;k<=n;k++)
				{
					if(i-k<1||j-k<1) break;
					s=l[i][j]-l[i-k-1][j-k-1];
					if(s+k>w) break;
					s+=r[i][j-k]-r[i-k-1][j+1];
					if(k%2==1)
						s-=mat[i-k/2][j-k/2];
					if(s<=w) ans=k; 
				}
			}
		}
		out<<ans<<"\n";
		
	}
	return 0;
}