Given a grid of size $n \times m$, the grid contains $c$ obstacles.
Two cells without obstacles are considered connected if they share an edge, or if they are connected through a series of cells without obstacles in between.
Determine the minimum number of obstacles that must be added to the grid to ensure that at least two cells without obstacles become disconnected.
### Input
- The first line contains a positive integer $T$, the number of test cases.
- For each of the $T$ test cases, the following lines are provided:
+ The first line consists of three positive integers $n, m, c$.
+ The next $c$ lines each contain two integers $x, y$, representing the position of an obstacle at row $x$ and column $y$.
### Output
- For each test case, print a non-negative integer representing the minimum number
### Example
Input:
```
4
4 4 2
1 1
4 4
2 3 1
1 2
2 2 2
1 1
2 2
1 1 0
```
Output:
```
2
1
0
-1
```
### Constraints
- $1 \le T \le 20$.
- $1 \le n,m \le 10^9$.
- $1 \le x \le n, 1 \le y \le m$.
- $1 \le c \le min(n \times m, 10^5), \sum{c} \le 10^5$.
