| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 82 | 44 | 23 | 62.162% |
A prefix-free set is a set of words in which no element is a prefix of another element in the set. For example {"hello"} , {"hello", "goodbye", "giant", "hi"} and the empty set are examples of prefix-free sets. On the other hand, {"hello","hell"} and {"great","gig","g"} are not prefix-free. You will be given a set of words, and you must calculate the number of subsets of words that are prefix-free. Note that both the empty set and the entire set count as subsets.
The first line of the input gives an integer T, which is the number of test cases. Each test case starts with a line containing N the number of words in the set. N is between 1 and 62 inclusive. Each of the next N line contains a word. The word contains only lowercase letter and length will not exceed 100.
For each test case, the output contains a line in the format Case #x: M, where x is the case number (starting from 1) and M is the number of prefix free subsets.
3 3 hello hell hi 4 a b c d 6 a ab abc abcd abcde abcdef
Case #1: 6 Case #2: 16 Case #3: 7