301829: CF345G. Suffix Subgroup
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
G. Suffix Subgrouptime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
You are given a group of n strings: s1, s2, ..., sn.
You should find a subgroup si1, si2, ..., sik (1 ≤ i1 < i2 < ... < ik ≤ n) of the group. The following two conditions must hold:
- there exists a string t such, that each string from found subgroup is its suffix;
- the number of strings in the found subgroup is as large as possible.
Your task is to print the number of strings in the found subgroup.
InputThe first line contains an integer n (1 ≤ n ≤ 105) — the number of strings in the group. Each of the next n lines contains a string. The i-th line contains non-empty string si.
Each string consists only from lowercase Latin letters. The sum of all strings si doesn't exceed 105.
OutputOutput a single integer — the number of strings in the found subgroup.
ExamplesInput6Output
bb
bb
b
aaa
aa
z
3Note
Look at the test sample. The required subgroup is s1, s2, s3.