U enigmatici, piramida je tip mozgalice koji treba da se popuni sa ~P~ reči u ~P~ redova. Da bi se pravilno popunila, počinje se od prve reči koja se sastoji od samo jednog slova. Svaka naredna reč ima jedno slovo više od prethodne i može da se dobije dodavanjem jednog slova, a zatim proizvoljnim menjanjem redosleda dobijenih slova.

Vama je dat niz od ~N~ stringova koji se sastoje od velikih slova engleske abecede. Ovi stringovi ne moraju nužno biti reči nekog jezika, već mogu biti proizvoljni nizovi slova. Pritom, ~k~-ti string ima dužinu tačno ~k~. Vaš zadatak je da odredite najveći prirodan broj ~P~ takav da prvih ~P~ stringova čini piramidu.

Opis ulaza

Prva linija standardnog ulaza sadrži jedan prirodan broj ~N~ - broj stringova. Narednih ~N~ linija sadrži po jedan string (~k~-ti string će biti dužine tačno ~k~), odnosno niz velikih slova engleske abecede.

Opis izlaza

U prvu i jedinu liniju standardnog izlaza ispisati najveći prirodan broj ~P~ takav da prvih ~P~ stringova čini piramidu.

Primer 1

Ulaz

7
A
AR
RAK
TRKA
KARTA
ARTIKL
AKROLIT

Izlaz

5

Primer 2

Ulaz

3
A
BC
DEF

Izlaz

1

Objašnjenje primera

U prvom primeru, najveća piramida koja može da se dobije se sastoji od prvih ~5~ stringova. Naime, reč _ARTIKL_ ne može da se dobije dodavanjem jednog slova reči _KARTA_ i menjanjem redosleda slova u rezultatu.

U drugom primeru najduža piramida se sastoji samo od prve reči.

Ograničenja

U svim test primerima važi: ~N \leq 2500~. Test primeri su podeljeni u 4 disjunktne grupe:

• U test primerima vrednim 20 poena: ~N \leq 10~.
• U test primerima vrednim 20 poena: ~N \leq 100~.
• U test primerima vrednim 20 poena: Svi stringovi sadrže samo slova _A_ i _B_.
• U test primerima vrednim 40 poena: Nema dodatnih ograničenja.

Napomena

Engleska abeceda se sastoji od sledećih slova: ABCDEFGHIJKLMNOPQRSTUVWXYZ. _ASCII_ vrednosti ovih karaktera su od ~65~ za veliko slovo _A_ do ~90~ za veliko slovo _Z_.