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 string ``princessruiruiprincessruirui" 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 into ``bcda", ``cdab" or ``dabc".

Input

The first line contains an integer $t~(1\le t\le 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\le k\le 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\times 10^8$. 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$.

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

Case #1: 51
Case #2: 21
Case #3: 0

Hint

In the first test case, the string S is ``zrzrzrzrruiruicumt". The first pattern ``zrzrzrzr" is a prefix of S. The third one ``zrzrzrzrru" is a prefix of S as well. The fourth on can be shifted into ``zrzrzr" and the fifth one can be shifted into ``zrzrzrzrr". The sum of squares is 1^2 + 3^2 + 4^2 + 5^2 = 51.