Suffix Subgroup

2000ms

262144K

Description:

You are given a group of n strings: s₁, s₂, ..., s_n.

You should find a subgroup s_i₁, s_i₂, ..., s_{i_k} (1 ≤ i₁ < i₂ < ... < i_k ≤ 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.

Input:

The first line contains an integer n (1 ≤ n ≤ 10⁵) — the number of strings in the group. Each of the next n lines contains a string. The i-th line contains non-empty string s_i.

Each string consists only from lowercase Latin letters. The sum of all strings s_i doesn't exceed 10⁵.

Output:

Output a single integer — the number of strings in the found subgroup.

Sample Input:

6
bb
bb
b
aaa
aa
z

Sample Output:

Note:

Look at the test sample. The required subgroup is s₁, s₂, s₃.

Informação

Provedor Codeforces

Código CF345G