로다의 순간이동

태양계에는 행성 여덟 개와 왜소행성 하나가 있다. 여기에 잘 알려지지 않은 사실이 하나 더 있다. 곰을 닮은 작은 생명체가 사는 비밀 행성 S4가 존재하고, 이 생명체의 암호명은 로다(Loda)다. 이 사실은 외부에 철저히 감춰져 있지만, 단체 사베즈(Savez)는 헨리크 장군이 이끄는 조사팀을 보내 로다를 연구했다. 조사 결과 로다에게 순간이동 능력이 있다는 것이 밝혀졌고, 헨리크는 로다를 자기 군대에 들이고 싶어 한다.

로다 한 마리는 문자열 $N$개로 이루어진다. $i$번째 문자열을 $x_i$라고 하자. 로다가 하는 순간이동 횟수는 이 문자열들의 특별한 부분 수열 하나로 정해진다. 부분 수열은 연속할 필요가 없다. $i < j$인 두 문자열 $x_i$와 $x_j$가 같은 부분 수열에 함께 들어갈 수 있는 조건은, $x_j$가 $x_i$로 시작하면서 동시에 $x_i$로 끝나는 것이다. 순간이동 횟수는 조건을 만족하는 부분 수열 중 가장 긴 것의 길이다.

순간이동 횟수를 구하라.

첫째 줄에 문자열의 개수 $N$이 주어진다. 이어지는 $N$개의 줄에 문자열이 한 줄에 하나씩 주어진다. 각 문자열은 영어 대문자로만 이루어진다. 모든 문자열의 길이 합은 200만보다 작다.

첫째 줄에 로다가 하는 순간이동 횟수를 출력한다.

접두사와 접미사는 서로 겹쳐도 된다. 예를 들어 AAA는 AA로 시작하면서 AA로 끝난다.

부분 수열에 들어가는 문자열끼리 서로 같아도 된다.