File Retrieval#5745
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 perform a search, you specify a key, which is also a non-empty string of lowercase letters. The result is a list of all files that contain the key as a substring. A string is a substring of a string if contains all characters of as a contiguous sequence. For example, "", "", "", and "" all contain "" as a substring, while "", "", "", and "" 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, compute the number of non-empty searchable subsets.
Each test case is described using several lines. The first line contains an integer representing the number of files on your hard disk (1 \le F \le 60). Each of the next lines contains 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 standard lowercase letters (from '' to '').
The last test case is followed by a line containing a single zero.
For each test case, output a line with an integer representing the number of non-empty searchable subsets.
Пример 1