Migrated from Lutece 669 One million ways to make love

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is no true love falling from the sky. So if you want to get into God Luo's heart, you must take action. As we all know, if you don't try to love, love will never come into being. There are one million ways to get the relationship between you and God Luo. If you find one of them, your dream about love will come true.

You know, God Luo always changes his necklace. This time, God Luo gets some magical beads and there are $10$ kinds of these beads. We use A to denote the first kind of the beads, B to denote the second, and so on.

The beads can do some transformation: You can put some beads in a special vessel and whisper a secret spell (Only God Luo knows it), and then these beads will become one new bead (Remember, before whispering the spell, there are at least two beads ).

God Luo gives the spell book to you, and this book is about something like this: BC -> D. It indicates that a B-Bead and a C-Bead can become a D-Bead (Only if you have the special vessel and know the spell).

After reading the spell book, you found an important fact: The right part can never be the same in any two spells (That is to say, every right part is distinct).

God Luo wants to make a necklace whose components are known (At least one bead). You think it's a chance to date God Luo, so you plan to tell God Luo the maximum necklace can be made from the beads that he has. Maybe the right answer to that question is one of the ways to love, so it's worth a try, isn't it?

CODE RIGHT NOW! FOR GOD LUO!

Input

There is an integer $T$ ($T\leq 100$) in the first line, indicating the number of test cases.

The first line of each test case contains $10$ integers (no more than $50$) indicating the number of each kind of beads that God Luo has.

The second line contains $10$ integers (no more than $50$), indicating the need for each kind of bead to compose the necklace.

The third line contains an integer $n$ ($0\leq n\leq 10$), indicating there are $n$ spells in total.

Then $n$ lines follow, and there are two strings in each line. The first string is the left part of the spell, and the second is the right part.

Notice:

1. The length of the second string is always $1$.
2. The length of first string is $L$ which satisfies that $2\leq L\leq 10$.
3. The right part of each line is distinct, while some left parts can be the same.

Output

For each test case, output the maximum number of necklaces that can be made from the initial beads.

Samples

2
2 2 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
0
2 2 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
3
AB C
AAA A
AAB B

2
2

Resources

罗神粉丝俱乐部