Longest Rhyming Sequence

Given N strings, define the longest common suffix (LCS) of two strings \(A\) and \(B\) as the length of the common suffix they share. Two strings \(A\) and \(B\) are said to rhyme if \[ \text{LCS}(A,B) \geq \max(|A|,|B|)-1, \] where \(|A|\) and \(|B|\) denote the lengths of \(A\) and \(B\) respectively.

You are given N strings. Your task is to select a sequence of these strings (each string used at most once) such that every pair of consecutive strings in the sequence rhymes. The goal is to maximize the length of the sequence (i.e. the number of strings in the sequence). Output the maximum possible sequence length.

inputFormat

The first line contains an integer N, the number of strings.

Then follow N lines, each containing a non-empty string.

outputFormat

Output a single integer, the maximum length of a sequence in which every adjacent pair of strings rhymes.

sample

3
abc
xbc
ayc

2