Ciobănaşul Ion a devenit pasionat de fotografierea peisajelor din jurul stânei lui şi mai nou, după cumpărarea unui calculator, este pasionat şi de prelucrarea acestor imagini.
Acum, Ion are un set de t poze, numerotate de la 1 la t. Ion a codificat fiecare poză ca matrice dreptunghiulară de numere naturale, în care reţine culoarea fiecărui pixel din poză.
Pentru fiecare poză, Ion analizează zone de formă pătrată şi observă că “modelul” din anumite zone apare în poză de mai multe ori. Apariţiile pe care el le observă nu sunt neapărat disjuncte, ele se pot suprapune parţial.
Acum Ion vrea să determine pentru fiecare poză i lungimea maximă a laturii unei zone pătrate al cărei model apare în poza i de cel puţin ki ori, fără rotaţii. Lungimea laturii unei zone pătrate este egală cu numărul de linii (acelaşi cu numărul de coloane) ale zonei.

Cerinţă

Scrieţi un program care să determine pentru fiecare poză i din set lungimea maximă a laturii unei zone de formă pătrată al cărei model apare în poză de cel puţin ki ori.

Date de intrare

Fişierul poze.in va conţine pe prima linie un număr întreg t, reprezentând numărul de poze. În următoarele linii ale fişierului se vor afla descrierile celor t poze. Descrierea unei poze va începe cu o linie ce conţine trei numere naturale n m k, separate prin câte un spaţiu, unde n reprezintă numărul de linii ale matricei, m numărul de coloane ale matricei, iar k numărul minim dorit de apariţii ale zonei pătrate. Următoarele n linii vor conţine câte m numere naturale separate prin spaţii ce reprezintă culorile pixelilor pozei.

Date de ieşire

Fişierul poze.out va conţine exact t linii. Linia i va conţine un întreg reprezentând lungimea maximă a laturii unei zone pătrate ce apare în poza i de cel puţin ki ori.

Restricţii

1 ≤ t ≤ 5
1 ≤ n, m ≤ 300
2 ≤ k ≤ 5
Culorile pixelilor sunt numere naturale ≤ 30000

Exemple

poze.in	poze.out	Explicaţii
3 4 4 2 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 3 3 2 3 0 1 0 3 0 1 0 3 3 3 5 0 0 1 0 0 1 1 1 2	2 2 1	Pentru prima poză, modelul din zona pătratică de latură 2 cu colţul stânga-sus în poziţia (1,3) apare de două ori. Pentru cea de a doua poză, modelul din zona pătratică de latura 2 cu colţul stânga-sus în poziţia (1,1) apare de două ori. Pentru cea de a treia poză, nu există nici o zonă pătratică al cărei model să apară de cel puţin 5 ori, deci lungimea maximă a laturii este 0

autor: Cosmin Negruşeri

propunător: Prof. Emanuela Cerchez

Liceul de Informatica ″Grigore Moisil″

emanuela.cerchez@gmail.com