Вам задан набор s1, s2, ..., sn, состоящий из n строк.
Требуется найти такой поднабор этого набора si1, si2, ..., sik (1 ≤ i1 < i2 < ... < ik ≤ n), что выполняются два условия:
- существует строка t, такая, что все строки поднабора являются ее суффиксами;
- количество строк в поднаборе максимально.
Ваша задача, вывести количество строк в таком поднаборе.
Выходные данные
Выведите единственное целое число — количество строк в описанном поднаборе.
Примечание
В первом тестовом примере искомый поднабор состоит из трех строк: s1, s2, s3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
bb
bb
b
aaa
aa
z
|
3
|