#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define all(a) (a).begin(),(a).end()
#define pb push_back
#define sz(a) ((int)(a).size())
#define mp make_pair
#define fi first
#define se second

typedef pair<int,int> pint;
typedef long long ll;
typedef vector<int> vi;


#define MAX_N 1005

int n,w,a[MAX_N][MAX_N];
ll sum[2][MAX_N][MAX_N];

ll query(int i, int j, int s)
{
    ll ans=sum[0][i+s-1][j+s-1]-sum[0][i-1][j-1];
    ans+=sum[1][i+s-1][j]-sum[1][i-1][j+s];
    if (s&1)
        ans-=a[i+s/2][j+s/2];
    return ans;
}

int main()
{
    int tc;
    scanf("%d",&tc);
    while (tc--)
    {
        scanf("%d %d",&n,&w);
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
            {
                scanf("%d",&a[i][j]);
                sum[0][i][j]=a[i][j]+sum[0][i-1][j-1];
                sum[1][i][j]=a[i][j]+sum[1][i-1][j+1];
            }
        int ans=2;
        for (int i=1; i+ans-1<=n; i++)
            for (int j=1; j+ans-1<=n; j++)
                if (query(i,j,ans)<=w)
                {
                    ans++;
                    j--;
                }
        printf("%d\n",ans-1);
    }
    return 0;
}