G. Суффиксный поднабор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вам задан набор s1, s2, ..., sn, состоящий из n строк.

Требуется найти такой поднабор этого набора si1, si2, ..., sik (1 ≤ i1 < i2 < ... < ik ≤ n), что выполняются два условия:

  • существует строка t, такая, что все строки поднабора являются ее суффиксами;
  • количество строк в поднаборе максимально.

Ваша задача, вывести количество строк в таком поднаборе.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105) — количество строк в наборе. В каждой из следующих n строк записана строка. В i-той из них записана непустая строка si.

Все строки состоят только из строчных латинских символов. Суммарная длина заданных строк не превосходит 105.

Выходные данные

Выведите единственное целое число — количество строк в описанном поднаборе.

Примеры
Входные данные
6
bb
bb
b
aaa
aa
z
Выходные данные
3
Примечание

В первом тестовом примере искомый поднабор состоит из трех строк: s1, s2, s3.