文本压缩问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在这个问题里,我们考虑用一份编码来对一篇文本进行压缩。编码表的美一项包括两部分:要编码的字符串和对应的编码。编码是二进制的01串,用来代替文本中相应的字符串以实现编码压缩的目的。这些01串不一定是等长的。文本压缩所要考虑的问题是对给定的文本和编码表,求出能令整个文本编码的最短的二进制串的长度。下面是一些编码的例子。

文本:

abcdef 编码表: 


 

下面有3种不同的方式进行编码:方式1: 



 方式2: 


 方式3: 


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

Input

输入的第1行包含整数N,表示文本压缩问题的数目。每个文本压缩问题的描述的第1行是要压缩的文本,接下来是编码表,每项一行。为简化起见,我们假定文本只包含小写字母“a,b,c,...,z”。这样的文本的例子有:abcdef,thisisatextstring和programmingcontest。

Output

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

Sample Input

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

Sample Output

3
2

Hint

Source