#include <fstream>

using namespace std;
ifstream cin("plantatii.in");
ofstream cout("plantatii.out");
long long v[1005][1005];
int t,n,w;
long long sumpart1[1005][1005], sumpart2[1005][1005];
bool verif(int x)
{
    for(int i=x; i<=n; i++)
    {
        for(int j=x; j<=n; j++)
        {
            int i1=i-x+1, j1=j-x+1;
            long long s=sumpart1[i][j]-sumpart1[i1-1][j1-1]+sumpart2[i1][j]-sumpart2[i+1][j1-1];
            if(x%2==1)
                s-=v[i-x/2][j-x/2];
            if(s<=w)
            return 1;
        }
    }
    return 0;
}
int cautbin()
{
    int st=1, dr=n, bun=0;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(verif(mid))
            bun=mid, st=mid+1;
        else
            dr=mid-1;
    }
    return bun;
}
int main()
{

    cin>>t;
    for(int r=1; r<=t; r++)
    {
        cin>>n>>w;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                cin>>v[i][j];
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                sumpart1[i][j]=sumpart1[i-1][j-1]+v[i][j];
        for(int i=n; i>=1; i--)
            for(int j=1; j<=n; j++)
            sumpart2[i][j]=sumpart2[i+1][j-1]+v[i][j];
        cout<<cautbin()<<'\n';
    }
    return 0;
}