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
 - $0$, if one word is a suffix of the other,
 - 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.

-----Examples-----
Sample Input:
4
spaghetti
already
confetti
serengeti
Sample Output:
4

Source: kattis | Difficulty: MEDIUM


Solutions: