【题目描述】

我们准备根据一份文本编码表来对一篇文本进行压缩。编码表的每一项包括两部分：要编码的字符串和对应的编码。编码是二进制的01串,用来代替文本中相应的字符串以实现

编码压缩的目的。这些01串不一定是等长的。文本压缩所要考虑的问题是对给定的文本和编码表,求出能令整个文本编码的最短的二进制串的长度。下面是一些编码的例子。

文本：abcdef
编码表：
字符串 a abc abcd bcd def ef
编码 01 0 1011 1 10 11
方式1
a bcd ef
01 1 11
方式2
abc def
0 10
方式3
abcd ef
1011  11

很明显,方式2使得压缩后的文本的长度最短(长度为3)你的任务是找出编码后的文本最短长度。如果文本不能使用编码表进行编码,则返回0作为结果(例如,使用上面的编码表不能对文本abcxxx进行编码)。

【输入格式】compare.in

第1行是一个整数N,表示文本压缩问题的数目。每个文本压缩问题的描述的第1行是要压缩的文本(不超个210个字符),接下来是编码表,每项一行,不超过l00行。为简化起见,我们假定文本只包含小写字母“a,b,c,…,z”。

【输出格式】compare.out

对应每个文本的压缩问题,输出编码后的文本的最短长度。每个文本压缩问题答案占一行。

【输入输出样例】

2
abcdef
(a,01)
(abc,0)
(abcd,1011)
(bcd,1)
(def,10)
(ef,11)
aa
(a,1)
(ab,10)

3
2