Counting Safe Word Subsets

A set of words is defined to be safe if and only if no word in the set is a prefix of another word in the set. In other words, for any two distinct words a and b in the subset, neither a is a prefix of b nor b is a prefix of a holds. Formally, given a word w and another word v, we say that w is a prefix of v if $$ v = w + x, $$ for some (nonempty) string x (note that when w equals v, they are not considered in conflict). The empty set is considered safe.

You are given a set \( S \) consisting of n words. Your task is to compute the number of safe subsets of \( S \).

Example:
If \(S = \{a, ab, abc\}\), then the safe subsets are: \(\{\}\), \(\{a\}\), \(\{ab\}\), \(\{abc\}\). Hence, the answer is 4.

inputFormat

The input begins with an integer n (\(1 \le n \le 20\)), the number of words in the set. Each of the next n lines contains a nonempty string consisting of lowercase letters.

Example:

3
a
ab
abc

outputFormat

Output a single integer, the number of safe subsets of the given set.

Example Output:

4

sample

3
a
ab
abc

4