У енигматици, пирамида је тип мозгалице који треба да се попуни са \(P\) речи у \(P\) редова. Да би се правилно попунила, почиње се од прве речи која се састоји од само једног слова. Свака наредна реч има једно слово више од претходне и може да се добије додавањем једног слова, а затим произвољним мењањем редоследа добијених слова.

Вама је дат низ од \(N\) стрингова који се састоје од великих слова енглеске абецеде. Ови стрингови не морају нужно бити речи неког језика, већ могу бити произвољни низови слова. Притом, \(k\)-ти стринг има дужину тачно \(k\). Ваш задатак је да одредите највећи природан број \(P\) такав да првих \(P\) стрингова чини пирамиду.

Опис улаза

Прва линија стандардног улаза садржи један природан број \(N\) - број стрингова. Наредних \(N\) линија садржи по један стринг (\(k\)-ти стринг ће бити дужине тачно \(k\)), односно низ великих слова енглеске абецеде.

Опис излаза

У прву и једину линију стандардног излаза исписати највећи природан број \(P\) такав да првих \(P\) стрингова чини пирамиду.

Пример 1

Улаз

7
A
AR
RAK
TRKA
KARTA
ARTIKL
AKROLIT

Излаз

5

Пример 2

Улаз

3
A
BC
DEF

Излаз

1

Објашњење примера

У првом примеру, највећа пирамида која може да се добије се састоји од првих \(5\) стрингова. Наиме, реч ARTIKL не може да се добије додавањем једног слова речи KARTA и мењањем редоследа слова у резултату.

У другом примеру најдужа пирамида се састоји само од прве речи.

Ограничења

У свим тест примерима важи: \(N \leq 2500\). Тест примери су подељени у 4 дисјунктне групе:

• У тест примерима вредним 20 поена: \(N \leq 10\).
• У тест примерима вредним 20 поена: \(N \leq 100\).
• У тест примерима вредним 20 поена: Сви стрингови садрже само слова A и B.
• У тест примерима вредним 40 поена: Нема додатних ограничења.

Напомена

Енглеска абецеда се састоји од следећих слова: ABCDEFGHIJKLMNOPQRSTUVWXYZ. ASCII вредности ових карактера су од \(65\) за велико слово A до \(90\) за велико слово Z.