==Include(page="template/taskheader" task_id="custi")==

Directorul închisorii a terminat cu refacerea gardului. Acum lucrează la proiectul "Cuştilor de câini" şi l-a pus tot pe James Blond la partea cu calcule. Însă James se cam grăbeşte şi nu va mai zice toată povestea cu câinii şi cum trebuie să fie cuştile, dar v-a trimis un email cu problema lui insa transformata in ceva mai simplu: dându-se o matrice pătratică de mărime $N x N$ care conţine numai $0$ şi {$1$}, se cere determinarea numărului tuturor sub-matricelor de mărime $M x M$ ({$M ≤ N$}) care conţin numai elemente de {$1$}. Astfel pentru un anumit test trebuie să afişati $N$ linii, astfel:

Directorul inchisorii a terminat cu refacerea gardului si acum lucreaza la proiectul "Custilor de caini", si l-a pus tot pe James Blond la partea cu calcule. Insa James se cam grabeste si nu va mai zice toata povestea cu cainii si cum trebuie sa fie custile, dar va trimis un email cu problema lui insa transformata in ceva mai simplu, partea din e-mail care contine exact problema arata cam asa: danduse o matrice patratica $NxN$ care contine numai $0$ si {$1$}, se cere determinarea numarului tuturor sub-matricelor $MxM$ ({$M ≤ N$}) care contin numai elemente de {$1$}. Astfel pentru un anumit test trebuie sa afisati $N$ linii, astfel:

Linia {$1$}: câte submatrice de $1x1$ cu proprietatea enunţată există.

Linia {$1$}: cate submatrici de $1x1$ cu proprietatea enuntzata exista

...

Linia {$i$}: câte submatrice de $ixi$ cu proprietatea enuntată există.
..
Linia {$N$}: câte submatrice de $NxN$ cu proprietatea enunţată există.

Linia {$i$}: cate submatrici de $ixi$ cu proprietatea enuntzata exista
...
Linia {$N$}: cate submatrici de $NxN$ cu proprietatea enuntzata exista

h2. Date intrare

În fişierul $custi.in$ se găsesc:

In fiserul $custi.in$ se gasesc:

* pe prima linie numărul $N$
* pe următoarele linii este dată matricea, cu elementele despărţite printr-un spaţiu (vezi exemplul)

* pe prima linie numarul $N$
* pe urmatoarele linii e data matricea cu elementele despartite printr-un spatiu(vezi exemplu) cate $N$ valori pe linie

h2. Date ieşire

h2. Date iesire

Fişierul $custi.out$ are structura enunţată mai sus.

Fiserul $custi.out$ are structura enuntata mai sus.

h2. Restrictii si precizari:

* $1 ≤ N ≤ 1000$
* Pentru $20%-30%$ din teste $N ≤ 100$

* $N<1001$
* Pentru $20%-30%$ din teste $N<101$
* Sub-matricile se pot suprapune intre ele.

h2. Exemple:

Exemple:

table(example). |_. custi.in |_. custi.out |
| 5

h3. Explicatii

$18$ submatrice de $1x1$
$7$ submatrice $2x2$

$18$ submatrici de $1x1$
$7$ submatrici $2x2$

$1$ sumatrice $3x3$

$0$ submatrice $4x4$
$0$ sumatrice $5x5$, care conţin numai elemente de $1$
 
 
==Include(page="template/taskfooter" task_id="custi")==

$0$ submatrici $4x4$
$0$ sumatrici $5x5$,  care contin numai elemente de $1$
==Include(page="template/taskfooter" task_id="custi")==