跳蚤国王和蛐蛐国王在玩一个游戏。

他们在一个 �n 行 �m 列的网格上排兵布阵。其中的 �c 个格子中 (0≤�≤�⋅�)(0≤c≤n⋅m)，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。

我们称占据的格子有公共边的两只跳蚤是相邻的。

我们称两只跳蚤是连通的，当且仅当这两只跳蚤相邻，或存在另一只跳蚤与这两只跳蚤都连通。

现在，蛐蛐国王希望，将某些（零个，一个或多个）跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不连通。

例如：图 11 描述了一个 �=4n=4，�=4m=4，�=2c=2 的情况。

这种情况下蛐蛐国王可以通过将第二行第二列，和第三行第三列的两只跳蚤替换为蛐蛐，从而达成他的希望，如右图所示。并且，不存在更优的方案，但是可能存在其他替换两只跳蚤的方案。

你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成，你还需要最小化被替换的跳蚤的个数。

输入格式

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 �T，表示数据的组数。

接下来依次输入 �T 组数据，每组数据的第一行包含三个整数 �,�,�n,m,c。

接下来 �c 行，每行包含两个整数 �,�x,y 表示第 �x 行，第 �y 列的格子被一个蛐蛐占据。每一组数据当中，同一个蛐蛐不会被多次描述。

输出格式

对于每一组数据依次输出一行答案。

如果这组数据中，蛐蛐国王的希望不能被达成，输出 −1**−**1。否则，输出被替换的跳蚤的个数的最小值。

输入输出样例

输入 #1复制

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

输出 #1复制

2
1
0
-1

说明/提示

样例解释

第一组数据就是问题描述中的例子。

对于第二组数据，可以将第二行第二列的一只跳蚤替换为蛐蛐，从而使得存在两只跳蚤不连通，并且不存在更优的方案。

对于第三组数据，最初已经存在两只跳蚤不连通，故不需要再进行替换。

对于第四组数据，由于最多只有一只跳蚤，所以无论如何替换都不能存在两只跳蚤不连通。

数据范围

对于全部的测试点，保证 1≤�≤201≤T≤20。我们记 ∑�∑c 为某个测试点中，其 �T 组输入数据的所有 �c 的总和。对于所有的测试点，∑�≤105∑c≤105。

对于全部的数据，满足 1≤�,�≤1091≤n,m≤109，0≤�≤�×�0≤c≤n×m，1≤�≤�,1≤�≤�1≤x≤n,1≤y≤m。

每个测试点的详细数据范围见下表。表中的 �,�,�n,m,c 均是对于单个输入数据（而非测试点）而言的，也就是说同一个测试点下的 �T 组数据均满足限制条件；而 ∑�**∑**c是对于单个测试点而言的。为了方便阅读，“测试点”一列被放到了表格的中间而不是左边。

�,�n,m	测试点	�c
�∗�≤4n∗m≤4	11	�≤�∗�c≤n∗m
�∗�≤8n∗m≤8	22
�∗�≤15n∗m≤15	33
�∗�≤30n∗m≤30	44
�∗�≤100n∗m≤100	55
�∗�≤300n∗m≤300	66
�∗�≤103n∗m≤103	77
�∗�≤2×104n∗m≤2×104	88	�≤5c≤5
	99	�≤15c≤15
	1010	�≤30c≤30
�,�≤2×104,�∗�≤2×104n,m≤2×104,n∗m≤2×104	1111	∑�≤2×104**∑c≤2×10**4
�,�≤2×104,�∗�≤105n,m≤2×104,n∗m≤105	1212
�,�≤2×104,�∗�≤3×105n,m≤2×104,n∗m≤3×105	1313
�,�≤2×104,�∗�≤106n,m≤2×104,n∗m≤106	1414
�,�≤2×104,�∗�≤109n,m≤2×104,n∗m≤109	1515
�,�≤105n,m≤105	1616	∑�≤105**∑c≤10**5
�,�≤109n,m≤109	1717	�=0c=0
	1818	�≤1c≤1
	1919	�≤2c≤2
	2020	�≤3c≤3
	2121	�≤10c≤10
	2222	�≤30c≤30
	2323	�≤300c≤300
	2424	∑�≤2×104**∑c≤2×10**4
	2525	∑�≤105**∑c≤10**5