Longest Common Palindromic Substring

Given up to 50 strings with total length 1,000,000, find the length of the longest palindrome that occurs as a substring in every one of them.

Hard8StringString matchingBinary searchHash mapNo attempts yetTime limit1sMemory limit512 MB

Description

Examples2

Problem

You are given n strings consisting only of lowercase English letters. Write a program that finds the longest palindrome appearing as a substring in all n strings and prints its length.

A substring is a string cut out as one contiguous block of the original string.

A palindrome is a string that stays the same when reversed. For example, "ababa" is a palindrome, but "abcbd" is not.

Input

The first line contains a positive integer n, the number of strings. ( $1 \le n \le 50$ )

Each of the following n lines contains one string. Every string consists only of lowercase English letters, and no string is empty. The sum of the lengths of the n strings is at most $1,000,000$ .

Output

Print the answer on the first line. If no palindrome appears in all n strings, print 0.