Repetitions

Interview

Time limit3sMemory limit128 MB

Summary

Given up to five lowercase words of length at most 2000, find the length of the longest substring that appears as a contiguous fragment in every word.

Level: Medium5 of 10
Topics: String, Binary search, Hash map, String matching
Solved: No attempts yet

Problem

You are given a sequence of words over the alphabet ['a', ..., 'z']. Find the length of the longest string that occurs as a contiguous fragment in every one of the given words.

Write a program that:

reads the sequence of words from standard input,
computes the length of the longest string that occurs as a contiguous fragment in every given word,
writes the result to standard output.

Input

The first line of standard input contains an integer $n$ , where $1 \le n \le 5$ is the number of words. Each of the next $n$ lines contains one word formed from lowercase letters of the English alphabet ['a', ..., 'z']. The length of each word is at least $1$ and at most $2000$ .

Output

The output must consist of exactly one line containing a single integer equal to the length of the longest string that occurs as a contiguous fragment in every given word.

Examples1

Example 1
Input
```
3
abcb
bca
acbc
```
Expected output
```
2
```