使用数据压缩技术，长字符串 “ruiruiruiruiruirui” 可以被压缩为 “(ruirui)3” 或 “(rui)6”。为了简化该技术，不允许进行多重压缩。例如，我们不允许将字符串 “princessruiruiprincessruirui” 压缩为 “(princess(rui)2)2”。

现在，对于给定的字符串 $S$ 和 $k$ 个使用上述技术表示的模式串，我们想要识别出哪些模式串是 $S$ 的前缀。我们强调，作为字符串的模式串可以进行循环移位。例如，模式串 “abcd” 可以循环移位为 “bcda”、“cdab” 或 “dabc”。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 13$)，表示测试用例的数量。

对于每个测试用例，第一行是字符串 $S$。第二行包含整数 $k$ ($1 \le k \le 10$)，接下来的 $k$ 行列出了模式串，并分别标记为 $1$ 到 $k$。字符串 $S$ 和所有模式串仅包含小写字母、数字和括号。重复次数为不超过 $2 \times 10^8$ 的正整数。$S$ 的长度不超过 $11000$。每个模式串的长度也不超过 $11000$。我们保证每个 $T$ 的实际长度（即未压缩前的原始长度）小于 $S$ 的实际长度（即 $S$ 未压缩前的原始长度）。括号内给出的每个子串的长度不超过 $10$。

输出格式

对于每个测试用例，输出作为 $S$ 前缀的模式串的标签平方和。

样例

输入格式 1

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

输出格式 1

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

说明

在第一个测试用例中，字符串 $S$ 为 “zrzrzrzrruiruicumt”。第一个模式串 “zrzrzrzr” 是 $S$ 的前缀。第三个模式串 “zrzrzrzrru” 也是 $S$ 的前缀。第四个模式串可以循环移位为 “zrzrzr”，第五个模式串可以循环移位为 “zrzrzrzrr”。标签的平方和为 $1^2 + 3^2 + 4^2 + 5^2 = 51$。