Description

The words "waterproof" and "proofreading" have a common part "proof", which is the prefix of "proofreading" and the suffix of "waterproof". Given all possible pairs extracted from a list of words, your task is to find the length of the common suffix-prefix of a pair that is the longest one.

For example, if the list consists of "proofreading", "waterproof", and "ingredient", then the answer will be 5, since the common suffix-prefix for the pair of "waterproof" and "proofreading" contains 5 letters and is the longest, in comparison with the common suffix-prefix for the pair of "proofreading" and "ingredient", which is "ing" and has only 3 letters.

Input

There are multiple test cases (less than 500). Each case starts with an integer N indicating the number of words. The next N strings are the list of the words for this test case. Each word has at most M letters, all in lower-case.

case 1: 2 <= N <= 10, M=15
case 2: 2 <= N <= 20, M=15
case 3: 2 <= N <= 20, M=30
case 4: 2 <= N <= 30, M=30

Output

There should be one line after each test case. Each line shows an integer that represents the longest length of the common part for the best choice of word pair.

Sample Input  Download

Sample Output  Download

Tags

Discuss