Description

You might think that Earth is the only planet where life is going on, but it is not true. About 880,228 light years away from Earth, there is a big planet, Haden, where another kind of human beings exists.

Unfortunately, there is another creature living on Haden: a dragon. This dragon attacks villages to find food whenever it gets hungry. People are getting sick of being attacked and being harmed. Now, they decided to select one strong dragon slayer to kill the dragon.

As one of human beings living on Haden, you've seen a lot of disasters caused by the dragon and you want to become a good dragon slayer. Here's the first task that you are given:

You have an n by n chess board where n is even. This chess board looks regular except that it has a couple of red cells and yellow cells, not only black and/or white. You are going to place many of white rooks and/or black rooks on the chess board. Here are the rules:

• Each cell has a color of black, white, yellow, or red
• You cannot place any rooks on yellow cells
• You must place one rook (either black or white, your choice) on each red cell
• You may not place a black rook on a black cell
• You may not place a white rook on a white cell
• There should be no pair of two rooks with the same color that can attack each other. If two rooks with the same color are placed on the same row OR same column, they can attack each other.
• You must maximize the total number of rooks that you place on the board

Let's take a look at following examples.

On the left 6 by 6 chess board, you can place 6 black rooks and 6 white rooks as indicated as small circles. On the right board, it is a bit more complicated due to two red cells, but you can safely place the same number of rooks here, too. Since you can never place more than 2n rooks (n white rooks and n black rooks), this is the maximum number of rooks that you can place without violating any rules. Note that both examples don't have any yellow cells. Let's write a program to solve this task so that you can advance to the next round!

Input

A test set can have several test cases, and the number of test cases is given at the first line. Each test case starts with three integers, n, m, and k where n tells you the size of a chess board, m is the number of red cells on the board, and k is the number of yellow cells. Each of following m lines contains two integers (row number and column number, 0-based), representing a red cell on the board. Then, each of following k lines contains two integers, representing a yellow cell on the board. See the sample input for clarification. You may assume that any cell cannot be both yellow and red and that the same cell is not given more than once. For each test case, n, m, and k do not exceed 40, 10, and 1600, respectively.

Output

For each test case, output only one integer, the maximum possible number of rooks that you can place. If such placement doesn't exist, output 0.

4
6 0 0
6 2 0
2 1
5 5
2 0 2
0 0
0 1
2 3 1
0 0
0 1
1 1
1 0

12
12
2
3

Hint

It does not matter whether the left-top cell is black or white in this problem. However, if you want, here is a simple, nice way to determine the color of each cell: Cell (r, c) is white if and only if it is neither yellow nor red and r+c is odd. Cell (r, c) is black if and only if it is neither yellow nor red and r+c is even. Here, (r, c) means that the cell is on the r-th row and on the c-th column.

Source

POJ Monthly--2007.08.05, Hooyeon Lee (ltdtl@POJ), "I like dragons"