URI Online Judge | 1335

File Retrieval

ByPablo Ariel Heiber Argentina

Timelimit: 8

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.

Input

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 ≤ F ≤ 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 104 characters; each character is one of the 26 standard lowercase letters (from 'a' to 'z').

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

Output

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

Sample Input Sample Output

6
form
formal
malformed
for
man
remake
3
cool
cool
old
0

11
3