Se dă o matrice de mărime $N$ pe $N$ care conține litere ale alfabetului englez. Definim un drum dreapta-jos ca fiind un șir de celule ale matricei care începe cu celula $(1, 1)$, se termină cu celula $(N, N)$, iar pentru fiecare celulă $(x, y)$ din drum (exceptând ultima), succesoarea sa este fie $(x+1, y)$, fie $(x, y+1)$. Spunem că șirul de caractere generat de un drum în matrice este șirul obținut prin concatenarea valorilor celulelor drumului în ordine.

Cerință

Să se găsească 2 drumuri dreapta-jos care nu se intersectează (decât în celulele $(1, 1)$ și $(N, N)$) pentru care coeficientul de similaritate este maxim. Coeficientul de similaritate a 2 drumuri reprezintă numărul de poziții $i$ pentru care $a_i = b_i$, $0 \leq i < |a|$, unde $a$ și $b$ sunt șirurile generate de cele 2 drumuri.

Date de intrare

Prima linie conține valoarea lui $N$. Următoarele $N$ linii conțin câte $N$ litere mici ale alfabetului englez, reprezentând matricea.

Date de ieșire

Prima linie va conține coeficientul maxim de similaritate între 2 drumuri dreapta-jos care nu se interesectează decât în capete.

Restricții și precizări

• $1 \leq N \leq 300$
• Pentru teste în valoare de $20$ de puncte, $1 \leq N \leq 7$.
• Pentru teste în valoare de $50$ de puncte, $1 \leq N \leq 50$.
• Pentru teste în valoare de $80$ de puncte, $1 \leq N \leq 150$.

Exemplul 1

2drumuri.in

3
abe
cef
zfq

2drumuri.out

4

Explicație

Drumurile sunt:

• abefq: $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)$
• acefq: $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$

Exemplul 2

2drumuri.in

4
abcd
bcde
aaaa
zdef

2drumuri.out

5