Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

The operating system of your computer indexes the files on your hard disk based on their contents, and provides textual search over them. The content of each file is a non-empty string of lowercase letters. To do a search, you specify a key, which is also a non-empty string of lowercase letters. The result is a list of all the files that contain the key as a substring. A string s is a substring of a string $t$ if t contains all characters of s as a contiguous sequence. For instance, “foofoo”, “cafoo”, “foota” and “foo” all contain “foo” as a substring, while “foa”, “fofo”, “fioo” and “oofo” do not.

You know the content of each file on your hard disk, and wonder whether each subset of the files is searchable. A subset of the files is searchable if there exists at least one key that produces exactly the list of those files as a result. Given the contents of the files on your hard disk, you are asked to compute the number of non-empty searchable subsets.

Each test case is described using several lines. The first line contains an integer $F$ representing the number of files on your hard disk $(1 \leq F \leq 60)$. Each of the next $F$ lines indicates the content of one of the files. The content of a file is a non-empty string of at most $10^4$ characters; each character is one of the $26$ standard lowercase letters (from $\texttt{‘a’}$ to $\texttt{‘z’}$).

The last test case is followed by a line containing one zero.

For each test case output a line with an integer representing the number of non-empty searchable subsets.