测试数据来自 system/2499

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　我们准备根据一份文本编码表来对一篇文本进行压缩。编码表的每一项包括两部分：单词及其对应01编码。用单词的编码来代替文本中相应的单词以实现压缩文本的目的。这些01串不一定是等长的，文本压缩所要考虑的是对给定的文本压缩后的长度尽量小。

【输入格式】

　　第一行为整数T，表示有T组数据，每组数据的第一行为要压缩的文本，第二行为整数n，表示编码表的项数，接下来n行每行包含两个字符串，第一个字符串为编码单词，第二个字符串为对应单词的二进制编码。
　　注意：为简化起见，我们假定文本和编码表中的单词只包含小写英文字母。

【输出格式】

　　输出T行，每行对应一组数据的答案，如果文本不能使用编码表进行压缩编码，则输出 0 。

【输入输出样例】

　Input

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

　Output

3
2

【样例解释】

　　第一组数据的编码表如下：
　　　　
　　对于文本：abcdef，下面有三种不同的方式进行研所编码：
　　　
　　很明显，方式2 使得压缩后的文本长度最短（长度为 3）。

【数据限制】

　　对于 \(100\%\) 的数据满足：\(0 ≤ T ≤ 10，0 ≤ n ≤ 100\)，文本长度不超过1000，单词和01编码长度均不超过50。

【来源】

　　Mr.he