Pentru că nu au luat toți nota 10 la simulare, conducerea liceului a hotărât să pedepsească elevii într-un mod inuman: aceștia nu au mai avut voie să meargă la teatru și nici să mai citească din marii clasici ai literaturii. Singura lor mângâiere era o matrice cu $N$ linii și $N$ coloane care conţine numai litere mici ale alfabetului englez, pentru care trebuiau să identifice submatricele valabile. O submatrice este considerată valabilă dacă îndeplineşte simultan următoarele condiţii:

• are cel puțin două linii și cel puțin două coloane
• literele aflate în colţurile stânga-sus şi dreapta-jos ale submatricei sunt strict mai mari lexicografic decât toate celelalte litere din submatrice.

Cerinţa

Ajutați elevii liceului să afle numărul submatricelor valabile care există în matrice și să scape astfel de pedeapsa îngrozitoare.

Date de intrare

Fişierul ssdj.in conţine pe prima linie numărul natural $N$, iar pe următoarele $N$ linii se află câte $N$ litere mici, neseparate prin spații.

Date de ieșire

Fişierul ssdj.out conţine un singur număr natural reprezentând numărul de submatrice valabile.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$
• Pentru teste valorând $10$ puncte, $N \leq 50$
• Pentru teste valorând $20$ puncte, matricea va conţine numai literele a şi b

Exemplu

ssdj.in

4 
maea
bcda
aaae
aaaa

ssdj.out

3

Explicație

Submatricele valabile sunt:

ma
bc 

ea
da
ae

da
ae