The following languages are only available languages for the problems from the contest

Friday the 13th, Programmers Day:

- Ada GNAT 4

No tag edit access

G. Suffix Subgroup

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a group of *n* strings: *s*_{1}, *s*_{2}, ..., *s*_{n}.

You should find a subgroup *s*_{i1}, *s*_{i2}, ..., *s*_{ik} (1 ≤ *i*_{1} < *i*_{2} < ... < *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^{5}) — 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^{5}.

Output

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

Examples

Input

6

bb

bb

b

aaa

aa

z

Output

3

Note

Look at the test sample. The required subgroup is *s*_{1}, *s*_{2}, *s*_{3}.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/25/2018 13:41:54 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|