G. Perfect Word
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given $$$n$$$ strings and required to find the length of the longest perfect word.

A string $$$t$$$ is called a perfect word, if and only if every non-empty substring of $$$t$$$ appears in the given strings.

A string $$$s$$$ is called a substring of $$$t$$$ if and only if it can be obtained by removing several (possibly zero) characters from the beginning or end of $$$t$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10 ^ 5$$$).

Each of the next $$$n$$$ lines contains a string consisting of lowercase English letters.

It is guaranteed that the total length of the given strings is no more than $$$10 ^ 5$$$.

Output

Output an integer, representing the length of the longest perfect word.

Example
Input
4
a
t
b
ab
Output
2