15893번 - 가장 긴 공통부분 팰린드롬

문제

알파벳 소문자로만 이루어진 문자열 n개가 주어진다. n개의 문자열에 모두 포함되어있는 부분 팰린드롬 중 가장 길이가 긴 것을 찾아 그 길이를 출력하는 프로그램을 작성하시오.

부분 팰린드롬이란 어떤 문자열의 부분 문자열(substring) 중 팰린드롬인 것을 뜻한다.

팰린드롬이란 원래 문자열과 뒤집은 문자열이 같아지는 문자열을 뜻한다. 예를 들어 "ababa"는 팰린드롬이지만 "abcbd"는 팰린드롬이 아니다.

입력

첫 번째 줄에 문자열의 수를 나타내는 자연수 n이 주어진다. (1 ≤ n ≤ 50)

두 번째 줄부터 n개의 줄에 걸쳐 문자열이 하나씩 주어진다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 빈 문자열은 주어지지 않는다. n개의 문자열의 길이를 전부 합한 것이 1,000,000 이하임이 보장된다.

출력

첫 번째 줄에 문제의 정답을 출력한다. 만약 n개의 문자열에 모두 포함된 팰린드롬이 존재하지 않는다면 0을 출력한다.

제한

힌트