Coco wants to sell an $M \times N$ chocolate bar by dividing it into $1 \times 2$ or $2 \times 1$ pieces. However, one day, $K$ of Coco's friends came over and ate one $1 \times 1$ square of chocolate each. Help Coco determine the maximum number of $1 \times 2$ or $2 \times 1$ chocolate pieces that can be obtained from the remaining chocolate.

Input

The first line contains the number of test cases $T$. The following lines provide the $T$ test cases in order. Each test case starts with a line containing $M$, $N$, and $K$. $M$ is the width of the chocolate, and $N$ is the height. The next $K$ lines each contain the coordinates of the chocolate square eaten by a friend, given as width coordinate $m$ and height coordinate $n$. The coordinate of the top-left square is $(1, \,1)$, and the positions of the eaten squares are unique.

Output

For each test case, output the maximum number of $1 \times 2$ or $2 \times 1$ chocolate pieces that can be obtained from the remaining chocolate on a single line.

Examples

Input 1

4
4 4 0
4 4 2
1 1
4 4
4 4 4
1 1
4 4
2 3
3 4
4 4 4
1 2
2 1
3 3
4 4

Output 1

8
6
6
5

Note

$1 \le T \le 1000$, $4 \le M, N \le 1000$, $0 \le K \le 4$, $M$ and $N$ are multiples of $4$, $1 \le m \le M$, $1 \le n \le N$