File Search

Time limit5sMemory limit128 MB

Summary

Count how many non-empty subsets of the files can be exactly the result set of some substring query.

Level: Hard8 of 10
Topics: String, Trie, String matching, Combinatorics
Solved: No attempts yet

Problem

Most operating systems index files on a hard drive by their contents. Each file's content is a non-empty string of lowercase English letters.

To search you need a query. A query is also a non-empty string of lowercase English letters.

The search result is the set of all files that contain the query as a substring.

A string $s$ is a substring of a string $t$ if $s$ occurs contiguously inside $t$ . For example, "foofoo", "cafoo", "foota", and "foo" all contain "foo" as a substring, but "foa", "fofo", "fioo", and "oofo" do not.

Suppose you know the contents of every file on the hard drive. You want to determine which subsets of files are "searchable".

A subset of files is searchable if there exists a query whose search result is exactly that subset.

Given the contents of all files, write a program that counts the number of searchable subsets of files. A subset must be non-empty.

Input

The input consists of several test cases.

The first line of each test case contains the number of files $F$ on the hard drive ( $1 \le F \le 60$ ). Each of the next $F$ lines contains the content of one file. Each file's content consists only of lowercase English letters and has length at most $10^4$ .

The last line of the input contains a single $0$ .

Output

For each test case, print the number of searchable subsets of files on its own line.

Examples3

Example 1

Input

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

Expected output

11
3

Example 2
Input
```
2
abc
xyz
0
```
Expected output
```
2
```
Example 3
Input
```
3
a
b
ab
0
```
Expected output
```
3
```