Rhyming Words Sequence

Adrian loves the rhymes in poetry. He considers two words to rhyme if and only if the length of their longest common suffix (LCS) is at least the length of the longer word minus one. In other words, for two words \(A\) and \(B\) the condition is

[ \text{LCS}(A,B) \ge \max(|A|,|B|)-1, ]

where LCS denotes the longest common suffix.

Now Adrian has obtained \(N\) words. He wants to select as many words as possible and arrange them in a sequence (reordering is allowed) such that every two adjacent words in the sequence "rhyme" under the condition above.

Note: Two words of the same length rhyme if and only if their last \(\;|A|-1\;\) characters are identical; and two words whose lengths differ by one can rhyme only if the shorter word is identical to the longer word with its first character removed.

inputFormat

The first line contains an integer \(N\) (the number of words). The following \(N\) lines each contain a word (a nonempty string of letters).

outputFormat

Output a single integer representing the maximum number of words that can be selected to form a sequence where every two adjacent words rhyme.

sample

3
cat
at
hat

3