Prefix

Interview

Time limit2sMemory limit128 MB

Summary

Given up to 50 words, find the largest subset where no word is a prefix of another, using a trie and tree DP.

Level: Medium5 of 10
Topics: Trie, Dynamic programming, Tree, String
Solved: No attempts yet

Problem

A set of words is prefix-free if no word in the set is a prefix of another word in the same set. For example, {hello}, {hello, goodbye, giant, hi}, and the empty set are all prefix-free. However, {hello, hell} and {giant, gig, g} are not prefix-free.

Given a collection of N words, find the maximum possible size of a subset that is prefix-free.

Input

The first line contains the number of words N. N is a positive integer not greater than 50.

Each of the next N lines contains one word. Every word consists only of lowercase English letters and has length at most 50. The same word may appear more than once in the given collection.

Output

Print the answer on the first line.

Examples4

Example 1
Input
```
6
hello
hi
h
run
rerun
running
```
Expected output
```
4
```
Example 2
Input
```
6
a
b
cba
cbc
cbb
ccc
```
Expected output
```
6
```
Example 3
Input
```
6
a
ab
abc
abcd
abcde
abcdef
```
Expected output
```
1
```
Example 4
Input
```
3
topcoder
topcoder
topcoding
```
Expected output
```
2
```