//luam fiecare diagonala
//cautam subsecvente de numere care insumate dau mai putin de W
//verificam daca si cealalta diagonala a matricei pe care o formeaza da mai putin de W
//verificam daca suma celor 2 diagonale da mai putin de W

#include<fstream>
#include<stdio.h>
using namespace std;

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

int x[1000][1000];

int gaseste_matricea_speciala(int x[1000][1000], int n, int w){

    int latura = 0;
    //array in care vom pune diagonalele si un counter
    int counter = 0;
    for (int slice = 1; slice < 2 * n - 2; ++slice) {
    	//printf("Slice %d: ", slice);
    	int z = slice < n ? 0 : slice - n + 1;
        //lungimea sliceului
        int slice_size = slice - 2*z + 1;
        //printf("\n");
    	for (int j = z; j <= slice - z; ++j) {
            int sum = 0;
            int counter = 0;
            for(int it = j; it <= slice - z; it++){
                counter++;
                //printf("Counter = %d \n", counter);
                sum += x[it][slice - it];
                //printf("Number of items = %d and item = %d on position %d , %d\n", slice-z, x[it][slice - it], it, slice-it);
                //punem diagonala in arrayul nostru ca sa verifica daca are subsequence cu suma < W
                //printf("Bagam %d la pozitia %d \n", x[j][slice - j], counter);
                //printf("it = %d j = %d \n", it, j);
                if(sum <= w && it > j){
                    int second_sum = 0;
                    if(it - j > latura){
                        //avem coordonatele in matrice: x[it][slice - it]. aflam corespondentul in cealalta diagonala
                        //printf("Opusul este numarul: %d \n", x[it][slice-it+counter-1]);
                        //printf("Urmatorul numar pe diagonala secundara: %d \n", x[it-1][slice-it+counter-1-1]);
                        for(int secundara = 0; secundara < counter; secundara++)
                            second_sum += x[it-secundara][slice-it+counter-1-secundara];
                            if (second_sum + sum > w)
                                break;
                    }
                    if (second_sum + sum <= w){
                        latura = counter;
                        //printf("S-a gasit submatricea speciala");
                    }

                }


            }
    return latura;
}
    }
}

int main(){
    printf("Test1");
    int t = 0, n = 0, w = 0;
    in>>t;

    for(int numar = 0; numar < t; numar++){
        in>>n;
        in>>w;
        //citim matricea
        for(int a = 0; a < n; a++)
            for(int b = 0; b < n; b++)
                in>>x[a][b];
       out<<gaseste_matricea_speciala(x,n,w)<<"\n";
    }
}