Fencing the cows

Problem Description

Little ColdHand wants to build a fence to enclose his cows' grazing area. However, in order for the fence to be effective, it must include all $m$ grass locations. Otherwise, the cows might rebel against him. To address this issue, Little ColdHand sought assistance from the Interstellar Cow Company. However, the company provided him with only $n$ fence points, and he can only build the fence from a point to another point. The final cost will be the number of points used. Little ColdHand is aware that the most cost-effective fence would be a convex hull, but he doesn't know the exact number of points required for it. Therefore, he has approached you to help solve this problem: Determine the minimum number of points needed to construct a fence that completely encloses all $m$ grass-eating locations. P.S. If the fence intersects any of the grass locations, we do not consider those locations as fully enclosed.

Input

The first line of input contains the integer $T$ ($1 \le T \le 10$), the number of test cases. The description of test cases follows. The first line of each test case contains two integers, $n$ and $m$ ($1 \le n \le 500, 1 \le m \le 500$) — the number of fence points and the number of grass locations. Each of the next $n$ lines contains the description of fence points. Each line contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i,y_i \le 10^9$), describes the fence point $a_i$ at ($x_i, y_i$). Each of the next $m$ lines contains the description of grass location. Each line contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i,y_i \le 10^9$), describes the grass location $b_i$ at ($x_i, y_i$). it is guaranteed that the sum of $n$ and $m$ over all test cases both do not exceed $4000$.

Output

For each test case, if any solution exists, output an integer in a line, indicating the minimum cost of fence. otherwise, output $-1$

Sample Input

2
4 1
1 1
1 -1
-1 1
-1 -1
0 0
4 1
1 1
1 -1
-1 1
-1 -1
1 0

Sample Output

4
-1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（2）