시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB2715337.500%

문제

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.

예제 입력 1

3
3
hello
hell
hi
4
a
b
c
d
6
a
ab
abc
abcd
abcde
abcdef

예제 출력 1

Case #1: 6
Case #2: 16
Case #3: 7