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.
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$.
An integer, the maximal rhyme power.
|Sample Input 1||Sample Output 1|
4 spaghetti already confetti serengeti
|Sample Input 2||Sample Output 2|
8 its not impossible cuz i know its possible