5509：Pattern String

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".

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$.

For each test case, output the sum of labels' squares for patterns as the prefix of $S$.