Powszechnie wiadomo, że wyraz jest palindromem, jeżeli czytany wspak brzmi tak samo jak czytany normalnie. Można też powiedzieć, że taki wyraz składa się z dwóch części składowych (lewej i prawej), które są względem siebie "symetryczne". W przypadku, gdy wyraz ma parzystą liczbę znaków, te dwie składowe to po prostu lewa i prawa połowa wyrazu, np. abba=ab+ba. Jeżeli palindrom ma nieparzystą liczbę liter, to przyjmijmy, że te "symetryczne" części uzyskamy usuwając środkową literę. Np. w wyrazie kajak, lewa składowa to ka, a prawa to ak. Oczywiście jest też możliwe, że składowe palindromu, również są palindromami. Np. w wyrazie oko, obie części to jednoliterowy wyraz o, który przecież sam jest też palindromem.

Zdefiniujmy więc teraz palindrom wielokrotny.

1. Każdy jednoliterowy wyraz jest palindromem jednokrotnym.
2. Jeżeli wyraz W jest palindromem n-krotnym, to wyraz P=W+W (tu + oznacza oczywiście konkatenację) oraz wyraz Q=W+c+W (gdzie c to dowolny pojedynczy znak) są palindromami (n+1)-krotnymi.
3. Każdy wyraz, którego normalnie nie nazwalibyśmy palindromem, będzie teraz palindromem 0-krotnym. 

Kilka przykładów palindromów i ich krotności:
  abc 0
  kajak 1
  oko 2
  oooo 3
  aabaacaabaa 4 

Napisz program, który wyznaczy krotność każdego z danych n palindromów, a następnie wśród otrzymanych wyników (oznaczmy je k_i, dla i=1..n) znajdzie pewną charakterystyczną wartość x, spełniającą jednocześnie dwa warunki:
  1. Co najmniej połowa liczb k_i jest większa lub równa x.
  2. Co najmniej połowa liczb k_i jest mniejsza lub równa x. 
Jeśli jest wiele liczb spełniających te warunki, należy wybrać najmniejszą. 

Wejście

W pierwszej linii liczba n (0 < n ≤ 500000) oznaczająca liczbę palindromów.
W każdej z kolejnych n linii jeden palindrom (ciąg małych liter angielskiego alfabetu) o długości d (0 < d ≤ 5000000).

Suma długości wszystkich palindromów nie przekracza 5000000.

Wyjście

Jedna liczba całkowita będąca szukaną wartością x.

Przykład

Wejście:
6
kajak
bbcbbabbcbb
oko
otomoto
abaoboubuaba
zzzz

Wyjście:
2