题目背景

草萤有耀终非火，荷露虽团岂是珠？

题目描述

小 G 和小 Z 在一个 $n$ 行 $m$ 列的网格图上摆满了熄灭的灯，并在其中 $k$ 盏灯中放置了燃料。但是它们均没有被点燃。我们用 $(i,j)$ 表示从下往上第 $i$ 行从左往右第 $j$ 列的格子。

这些灯在点亮时会出现某些奇怪的现象：假设 $a,b,x,y$ 均为正整数，当 $(x,y),(x+a,y),(x,y+b),(x+a,y+b)$ 四个格子中有三个格子中的灯都已点亮且 $1 \le x < x+a \le n,1 \le y < y+b \le m$，那么剩下的那一个格子的灯就会自动被点亮。

因此，一盏灯既可以在一开始时通过点燃燃料的方式点亮，又可以通过这种现象点亮。

现在他们想要把放有火炬台的格子 $(1,1)$ 和 $(1,m)$ 中的灯点亮。而你需要求出把格子 $(1,1)$ 和 $(1,m)$ 中的灯都点亮时，一开始最少要点燃几盏灯中的燃料（不含过程中通过这种现象点亮的），或者报告无法把格子 $(1,1)$ 或 $(1,m)$ 中的灯点亮。

注意：同一盏灯中可能放置多个燃料，但只要点燃一个燃料这盏灯就可以被点亮。

输入格式

本题有多组测试数据。

第一行包含一个正整数 $t$，表示数据的组数。

对于每一组测试数据：

• 第一行包含三个整数 $n,m,k$，意义如上文所示。
• 接下来的 $k$ 行，每行两个正整数 $x,y$，表示第 $x$ 行第 $y$ 列的灯上放有一个燃料。

输出格式

对于每一组测试数据，一行输出一个整数，表示把格子 $(1,1),(1,m)$ 中的灯点亮时，一开始最少要点燃的燃料数。

若格子 $(1,1)$ 或 $(1,m)$ 中的灯无法点亮，则输出 $-1$。

1
5 5 7
3 1
2 2
5 4
4 4
3 4
1 4
3 5

4

1
5 5 7
1 1
3 1
3 3
2 3
4 3
2 5
4 5

5

1
5 5 3
1 1 
1 3
1 5

2

1
5 5 4
1 1
1 3
2 2
5 5

-1

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

1

提示

样例解释

对于第一组样例：可以选择格子 $(3,1),(3,4),(1,4),(3,5)$ 中的燃料点燃，如图 $1$ 所示。

对于第二组样例：可以选择格子 $(1,1),(3,1),(3,3),(2,3),(2,5)$ 中的燃料点燃，如图 $2$ 所示。

对于第三组样例：可以选择格子 $(1,1),(1,5)$ 中的燃料点燃。

对于第四组样例：显然没有合法的方案。

对于第五组样例：此时格子 $(1,1)$ 与 $(1,m)$ 是同一个格子，因此只要选择格子 $(1,1)$ 中的一个燃料点燃即可。并且注意数据中可能出现同一盏灯中有多个燃料的情况。

数据规模与约定

本题采用捆绑测试。

其中子任务 $0$ 为样例，记 $0$ 分。

Subtask 编号	$t\le$	$n,m \le$	$\sum n,\sum m \le$	$k \le$	$\sum k \le$	特殊性质	得分
$1$	$10$	$10$	$100$	$10$	$100$	无	$20$
$2$		$10^3$	$10^4$	$5\times 10^3$	$2\times10^4$	$A$	$2$
$3$	$5\times 10^3$	$10^5$	$10^6$	$5\times10^5$	$2\times10^6$	$B$
$4$				$5\times 10^5$		$C$	$15$
$5$	$10^3$		$10^4$	$5\times 10^3$	$2\times 10^4$	无	$26$
$6$	$5\times 10^3$	$10^5$	$10^6$	$5\times 10^5$	$2\times 10^6$		$35$

特殊性质 $A$：保证格子 $(1,1),(1,m)$ 放有燃料。
特殊性质 $B$：保证放置的燃料中没有两个燃料是同一行或者同一列的。
特殊性质 $C$：保证一定存在某一列摆满了燃料。

对于 $100\%$ 的数据：保证 $1 \le t \le 5\times10^3,1 \le n,m \le 10^5,0 \le k \le 2\times10^6,1 \le \sum n,\sum m \le 10^6,0 \le \sum k \le 2\times 10^6,1\le x \le n,1 \le y \le m$。