eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Суффиксный поднабор

Суффиксный поднабор

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Вам задан набор s_1, s_2, ..., s_n, состоящий из n строк.

Требуется найти такой поднабор этого набора, что выполняются два условия:

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

  • количество строк в поднаборе максимально.

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

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

В первой строке записано целое число n (1n10^5) — количество строк в наборе. В каждой из последующих n строк записана строка. В i-той из них записана непустая строка s_i. Все строки состоят только из строчных латинских символов. Суммарная длина заданных строк не превосходит 10^5.

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

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

Пример

Входные данные #1
6
bb
bb
b
aaa
aa
z
Выходные данные #1
3