There is an $n\times m$ grid where $c$ $(0\le c\le nm)$ cells are 1 cells and the rest of the cells are 0 cells.

We say two cells sharing an edge are adjacent. We say two 0 cells are connected if and only if the two 0 cells are adjacent or there exists a third 0 cell that is connected with both cells.

Now we want to replace some (zero, one, or multiple) 0 cells with 1 cells so that after the replacement there exist two 0 cells that are not connected with each other.

For example, if there is a $4\times 4$ grid where the top-left and the bottom-right corners are 1 cells and the rest are 0 cells, then it is optimal to replace 2 0 cells with 1 cells so that there exist two 0 cells that are disconnected from each other: for example, one possible solution is to replace the other two 0 cells on the diagonal connecting the top-left and the bottom-right corners.

You need to check if the goal can be achieved. If the goal can be achieved, you need to output the minimum number of 0 cells that should be made into 1 cells.

Input Specification

Each test input consists of multiple test cases. The first line of the input file consists of an integer $T$ denoting the number of test cases in the input file. $T$ test cases follow.

The first line of each test case consists of three integers $n,m,c$. In the following $c$ lines, each line consists of two integers $x,y$ denoting the cell on the $x$-th row and the $y$-th column is a 1 cell. The same 1 cell won't appear multiple times in the same test case.

Two neighboring integers in a line is separated by a space.

Output Specification

For each test case, output a line denoting the answer.

If in the test case, it is impossible to disconnect two 0 cells, output -1. Otherwise, output the minimum number of 0 cells that should be replaced by 1 cells.

Sample Input 1

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

Sample Output 1

2
1
0
-1

Explanation for Sample 1

The first test case is the scenario described in the problem description.

For the second test case, it is possible to replace the cell on the second column of the second row with a 1 cell so that there exist two disconnected 0 cells.

For the third test case, since there are two disconnected 0 cells at the beginning, output 0.

For the fourth test case, there is only one 0 cell at the beginning so it is impossible to have two disconnected 0 cells. As a result, the output should be -1.

Attachment Package

The samples are available here.

Sample 2

See ex_grid2.in and ex_grid2.ans.

Constraints

For all test cases, $1\le n,m\le {10}^9$, $0\le c\le min(nm,{10}^5)$, $1\le x\le n$, $1\le y\le m$, $1\le T\le 20$.

Let $\sum c$ denote the sum of $c$ among the $T$ test cases in an input file. It is guaranteed that $\sum c\le {10}^5$.

Test case	$n,m$	$c$
1	$nm\le 4$	$c\le nm$
2	$nm\le 8$
3	$nm\le 15$
4	$nm\le 30$
5	$nm\le 100$
6	$nm\le 300$
7	$nm\le 1000$
8	$nm\le 20000$	$c\le 5$
9		$c\le 15$
10		$c\le 30$
11	$n,m\le 20000$, $nm\le 20000$	$\sum c\le 20000$
12	$n,m\le 20000$, $nm\le {10}^5$
13	$n,m\le 20000$, $nm\le 3\times {10}^5$
14	$n,m\le 20000$, $nm\le {10}^6$
15	$n,m\le 20000$, $nm\le {10}^9$
16	$n,m\le {10}^5$	$\sum c\le {10}^5$
17	$n,m\le {10}^9$	$c=0$
18		$c\le 1$
19		$c\le 2$
20		$c\le 3$
21		$c\le 10$
22		$c\le 30$
23		$c\le 300$
24		$\sum c\le 20000$
25		$\sum c\le {10}^5$