#include <fstream>

using namespace std;
ifstream cin("plantatii.in");
ofstream cout("plantatii.out");
long long int v[1005][1005];
long long 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++)
        {
            long long s=sumpart1[i][j]-sumpart1[i-x][j-x]+sumpart2[i-x+1][j]-sumpart2[i+1][j-x];
            if(x%2==1)
                s-=v[i-x/2][j-x/2];
            if(s<=w)
                return 1;
        }
    }
    return 0;
}
int cautbin_par()
{
    int st=1, dr=n/2, bun=0;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(verif(2*mid))
            bun=2*mid, st=mid+1;
        else
            dr=mid-1;
    }
    return bun;
}
int cautbin_imp()
{
    int st=0, dr=n/2, bun=0;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(verif(2*mid+1))
            bun=2*mid+1, 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<<max(cautbin_par(), cautbin_imp())<<'\n';
    }
    return 0;
}