Description

A set of words is safe if and only if no word is a prefix of another word; this ensures that the data is not easily misunderstood. Now you have a word set $S$, and you need to count how many of its subsets are safe.

Note that the empty set is always safe.

Input Format

The first line contains an integer $n$, the size of the set. Then $n$ lines follow. Each line contains a string consisting of \verb!a!\cdots\verb!z!.

Output Format

The number of safe subsets.

3
hello
hell
hi

6

Hint

Constraints and Conventions

• For $30\%$ of the testdata, it holds that $1 \le n \le 10$.
• For $100\%$ of the testdata, it holds that $1 \le n \le 50$, string length $\le 50$, and no two strings are exactly the same.

Translated by ChatGPT 5