L. Onion Peeling
time limit per test
15 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a set of $$$N$$$ points on a 2D plane.

Onion Peeling is the process of repeatedly computing the Convex Hull of the remaining points, then removing those hull points. Each complete set of hull points removed in one iteration is called a layer. Let the convex hulls of the onion layers be $$$H_1, H_2, \dots, H_L$$$, where $$$H_1$$$ is the outermost layer (convex hull of all $$$N$$$ points) and $$$H_L$$$ is the innermost layer.

You are given $$$Q$$$ query points. For each query point $$$P$$$, determine how many onion layers strictly contain it. A point is strictly inside a convex polygon if it is in the interior, not on the boundary.

Specifically:

  • If $$$P$$$ is strictly outside $$$H_1$$$, output $$$0$$$.
  • If $$$P$$$ is strictly inside exactly $$$k$$$ hulls ($$$H_1$$$ through $$$H_k$$$), output $$$k$$$.
  • The maximum possible answer is $$$L$$$ (if $$$P$$$ is strictly inside all $$$L$$$ hulls).

A hull with $$$1$$$ or $$$2$$$ vertices has no interior — no point can be strictly inside it.

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 9$$$), the number of test cases. The description of $$$T$$$ test cases follows.

Each test case is described as follows:

The first line contains two integers $$$N$$$ ($$$1 \le N \le 5 \times 10^4$$$) and $$$Q$$$ ($$$1 \le Q \le 10^6$$$), where $$$N$$$ is the number of points and $$$Q$$$ is the number of queries. The sum of $$$N$$$ over all test cases in a file does not exceed $$$5 \times 10^4$$$, and the sum of $$$Q$$$ does not exceed $$$10^6$$$.

The next $$$N$$$ lines each contain two integers $$$x_i, y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — coordinates of the $$$i$$$-th point. All $$$N$$$ points are distinct and no three points are collinear.

The next $$$Q$$$ lines each contain two integers $$$x_j, y_j$$$ ($$$-10^9 \le x_j, y_j \le 10^9$$$) — coordinates of the $$$j$$$-th query point.

Output

For each test case, output $$$Q$$$ lines. The $$$j$$$-th line contains a single integer — the number of layers strictly containing the $$$j$$$-th query point.

Example
Input
1
12 5
0 0
12 1
12 12
1 12
8 3
10 5
5 7
8 10
9 5
9 6
3 9
5 4
0 0
6 6
-1 -1
13 6
12 12
Output
0
2
0
0
0