Witch's Cauldron (part 1)

A witch has a big cauldron, $N$ ingredients in various quantities, and $M$ recipes bestowed upon her by her grandmother.

Each recipe is represented by the list of ingredients, along with the quantity of each of them. For example, a recipe might require:

wool of bat (2)
eye of newt (1)
owlet's wing (3)

A recipe is good if, for every ingredient it requires, the witch has at least that many units of the ingredient available.

Given the list of ingredients and recipes, determine how many recipes are good.

Input

The first line contains an integer $T$ — the number of test cases.

Each test case begins with two integers $N$ ( $1 \leq N \leq 100$ ) and $M$ ( $1 \leq M \leq 100$ ).

The following $N$ lines list available ingredients, one per line, in the format ingredient name (quantity). Each quantity is between $1$ and $100$ .

The subsequent $M$ lines list recipes, one per line, in the format = ingredient name 1 (quantity), ingredient name 2 (quantity), .... Each recipe has between 1 and 10 ingredients.

All ingredient names consist of lowercase Latin letters, apostrophes ('), and spaces.

Output

For each test case $i$ , output a single line Case #i: num, where num is the number of good recipes in the corresponding test case.

Examples

Input

1
3 3
wool of bat (5)
eye of newt (1)
owlet's wing (3)
= wool of bat (2), eye of newt (1), owlet's wing (3)
= hobbit's nail (10)
= wool of bat (1), eye of newt (2), owlet's wing (2)

Output

Case #1: 1

Explanation

The witch has 3 ingredients: wool of bat in the quantity of 5, eye of newt in the quantity of 1, and owlet's wing in the quantity of 3.

She also has 3 recipes:

The first recipe requires 2 units of wool of bat, 1 unit of eye of newt, and 3 units of owlet's wing. We have enough of each of these ingredients, so it's a good recipe.
The second recipe requires 10 units of hobbit's nail. The witch does not have a single unit of this ingredient, so it's not a good recipe.
The third recipe requires 1 unit of wool of bat, 2 units of eye of newt and 2 units of owlet's wing. She only has 1 unit of eye of newt, so it's not a good recipe either.

Overall, only one recipe is good, so the answer is 1.