Problem C
Euphemisms-Shmeuphemisms

Image by Lewis Clarke (geograph), Used under license

As stated in Wikipedia, “A euphemism is a generally innocuous word or expression used in place of one that may be found offensive or suggest something unpleasant”. Thus, you are never lost, but “geographically mislocated”. Some other creative examples include “penetrating deliverer of kinetic energy” for bullet, and the now classic “enhanced interrogation methods”.

The administration of the local Bitville newspaper, being risk-averse and mindful of political correctness, introduces a list of forbidden words, along with the corresponding euphemisms to replace them with. Too late to teach an old dog new tricks! The staff members, who are supposed to replace the forbidden words with the officially endorsed equivalents, concurred on the following strategy instead: they will continue writing as they did before, but will simply remove some characters from their articles, so that no forbidden word appears in the text. After all, a Bitville text is merely a contiguous stretch of $0$s and $1$s, and as long as you remove the absolute minimum number of characters, you can hope no one will spot the difference! Your job is, given a list of forbidden words $w_1,w_2,\ldots ,w_ n$ and the text $T$ to edit, to find the minimum number of characters to remove from $T$, so that none of the strings $w_1,w_2,\ldots ,w_ n$ occurs as a substring in the text $T.$

Input

The first line contains an integer $ts, 1 \leq ts \leq 100$, denoting the number of test cases. Then follow $ts$ blocks, in the following format:

• a single line with an integer $n, 1\leq n \leq 30$ – the number of forbidden Bitville-words

• $n$ lines, each line containing a forbidden word $w_ i,$ with length $1 \leq |w_ i| \leq 13$

• finally, a line with the text $T$ to edit, with length $1 \leq |T| \leq 3000.$

Thus, a test case with $n$ forbidden words consists of $n+2$ lines. You are guaranteed that words and the text are non-empty, will not contain any leading or trailing blanks, and are composed of solely $0$s and $1$s.

Output

Per test case, a single line in the format “Case #t: ans”, where “t” stands for the number of the test case (starting from $1$), and “ans” is the answer to the problem, which is an integer indicating the minimum number of characters to remove for this test case.

3
2
0
1
101
1
0
111
2
01
010
1010

Case #1: 3
Case #2: 0
Case #3: 1