Description

The Flea King and the Cricket King are playing a game.

They are arranging their troops on an $n \times m$ grid. In $c$ of these cells ($0 \le c \le nm$), there is a cricket, and in the remaining cells, there is a flea.

We say two fleas are adjacent if the cells they occupy share a common edge.

We say two fleas are connected if and only if they are adjacent, or if there exists another flea that is connected to both of them.

Now, the Cricket King wishes to replace some (0, 1, or more) fleas with crickets such that, after the replacements, there exist at least two fleas that are not connected.

For example, if we use the symbol in Figure 1 to represent a flea and the symbol in Figure 2 to represent a cricket, then Figure 1 describes a case where $n=4, m=4, c=2$.

In this case, the Cricket King can achieve his wish by replacing the fleas at row 2, column 2 and row 3, column 3 with crickets, as shown in Figure 2. Furthermore, there is no better solution, although other solutions replacing 2 fleas may exist.

Figure 1

Figure 2

You need to first determine whether the Cricket King's wish can be achieved. If it can be achieved, you also need to minimize the number of fleas replaced.

Input

The input file is grid.in.

Each input file contains multiple test cases.

The first line of the input file contains a single integer $T$, representing the number of test cases. It is guaranteed that $1 \le T \le 20$.

Following this are $T$ test cases. The first line of each test case contains three integers $n, m, c$. It is guaranteed that $1 \le n, m \le 10^9$ and $0 \le c \le \min(nm, 10^5)$.

The next $c$ lines each contain two integers $x, y$, representing that the cell at row $x$, column $y$ is occupied by a cricket ($1 \le x \le n, 1 \le y \le m$). Within each test case, the same cricket will not be described more than once.

Integers on the same line are separated by a space.

Output

The output file is grid.out.

For each test case, output the answer on a single line.

If the Cricket King's wish cannot be achieved in a test case, output $-1$. Otherwise, output the minimum number of fleas to be replaced.

Examples

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

Output 1

2
1
0
-1

Note

The first test case is the example from the problem description.

For the second test case, one can replace the flea at row 2, column 2 with a cricket, such that there exist two fleas that are not connected, and there is no better solution.

For the third test case, there already exist two fleas that are not connected initially, so no replacement is needed.

For the fourth test case, since there is at most one flea, it is impossible for two fleas to be not connected regardless of how replacements are made.

Examples 2

See grid/grid2.in and grid/grid2.ans in the contestant directory.

Note

If your program requires a large stack space (which usually implies deep recursion), please be sure to read the stack.pdf document in the contestant directory to understand the stack space limits during final evaluation and how to adjust the stack space limit in your current working environment.

Subtasks

For all test cases, it is guaranteed that $1 \le T \le 20$. We denote $\sum c$ as the sum of all $c$ in the input data for a single test case. For all test cases, $\sum c \le 10^5$.

For all data, $1 \le n, m \le 10^9, 0 \le c \le nm, 1 \le x \le n, 1 \le y \le m$.

The detailed data ranges for each test case are shown in the table below. The values $n, m, c$ in the table refer to individual input data (not the entire test case), meaning all $T$ test cases under the same test point satisfy these constraints; while $\sum c$ refers to the entire test point. For readability, the "Test Point" column is placed in the middle of the table.