Problem Description
Using data compression technique, the long string ruiruiruiruiruirui" can be compressed into(ruirui)3" or (rui)6". To simplify the technique, multiple compressions are not allowed. For example, we don't allow to compress the stringprincessruiruiprincessruirui" into ``(princess(rui)2)2".
Now for given string S and k patterns using the mentioned technique, we want to distinguish each pattern which is a prefix of S. We emphasize that a pattern as a string can be cyclic shifted. For example, a pattern abcd" can be shifted intobcda", cdab" ordabc".
Input
The first line contains an integer t (1≤t≤13) which is the number of test cases.
For each test case, the first line is the string S. The second line contains the integer k(1≤k≤10) and following k lines list the patterns, labelled from 1 to k.
The string S and all patterns only contain lower-case letters, numbers and parentheses. Numbers of replication are positive integers no more than 2×108. The length of S is no more than 11000. The length of each pattern is no more than 11000 as well. We guarantee that the actual length of each T (the length of the original pattern without compression) would be smaller than the actual length of S (the length of original S without compression). The length of each substring given in parentheses is no more than 10.
Output
For each test case, output the sum of labels' squares for patterns as the prefix of S.
Sample Input
3
z(rz)3r(rui)2cumt
5
(zr)4
zrzrrui
zr(zr)2z(r)2u
(rz)3
(zr)2z(r)2zr
(ab)2aab(aba)3(ba)2(zhang)940712
4
(babaa)2(baa)2
(aabab)2
(ab)3
(aba)2(ab)3a(ab)2(a)2b
(a)100b(a)100c(a)100d
1
(a)100d(a)100c(a)100b
Sample Output
Case #1: 51
Case #2: 21
Case #3: 0
