Time Limit: 5000 MS    Memory Limit: 131072 K 


Description

You are solving a crossword puzzle and you have already written down the answers to all questions. While filling in the answers in the diagram, you notice that some answers have overlapping letters that do not match, so you must have made some mistakes in the answers. Instead of checking your answers, you decide to write a computer program to find the maximum number of answers that could have been correct.

Input

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format: ? One line with two integers H and V , satisfying 1 H, V 500: the number of horizontal and vertical words, respectively. ? H lines, one for each horizontal word, each with two integers x and y and a string W, satisfying 0 x, y 1, 000 and 1 Length(W) 1, 000: the location of the first letter and the answer. ? V lines, one for each vertical word, each with two integers x and y and a string W, satisfying 0 x, y 1, 000 and 1 Length(W) 1, 000: the location of the first letter and the answer. Integers and strings on the same line are separated by single spaces. No pair of horizontal words will overlap, nor will any pair of vertical words. The words consist of upper case letters only. The top left corner of the diagram is at x = y = 0, x runs in the horizontal direction, and y runs in the vertical direction (downwards).

Output

For every test case in the input, the output should contain a single number, on a single line: the maximum number of answers that can fit in the crossword.

Sample Input

2 2 2 0 1 BAPC 0 2 LEIDEN 0 0 SOLUTION 2 1 WINNER 1 4 0 1 HELLO 1 0 HI 2 0 BYE 3 0 GOODBYE 4 0 FAREWELL

Sample Output

3 4

Source

bapc 2010