Hide

Problem J
Rhyme Power

Languages en sv

Rhymes are complicated. The extent to which one word rhymes with another depends on how similar they sound; but if they are too similar then they aren’t considered a rhyme at all. Karim has a huge list of $N$ words and wants to determine the maximally rhyming pair of words. To that end he has introduced the concept of rhyme power:

Given two words $S$ and $T$, their rhyme power $r(S,T)$ is defined as

  1. $0$, if one word is a suffix of the other,

  2. the length of their longest common suffix, otherwise.

For instance, the rhyme power of “fire” and “desire” is $3$, because their longest common suffix “ire” has length $3$. In contrast, the rhyme power of “impossible” and “possible” is $0$, because “possible” is a suffix of “impossible”.

Given Karim’s list of $N$ words, your task is to find the maximum value of $r(S, T)$ over all pairs of words.

Input

The first line contains an integer $N$ with $2 \leq N \leq 10^5$, the number of words.

The following $N$ lines each contain a string $S_ i$, where $1 \leq |S_ i| \leq 10^6$. The sum of all string lengths $|S_ i|$ is at most $10^6$.

Output

An integer, the maximal rhyme power.

Sample Input 1 Sample Output 1
4
spaghetti
already
confetti
serengeti
4
Sample Input 2 Sample Output 2
8
its
not
impossible
cuz
i
know
its
possible
0