M. Are You High On Bisseh?
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a set of $$$n$$$ red points and $$$m$$$ blue points in the Euclidean plane. No three points, ignoring their colors, are collinear.

A subset of at least three red points is called good if its points form a strictly convex polygon (i.e., every point in the subset is a vertex of its own convex hull).

Let $$$P$$$ be the convex polygon defined by a good subset. A good subset is valid if the interior of $$$P$$$ contains an odd number of blue points. Calculate the total number of valid good subsets, modulo $$$2$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case starts with a line containing two integers $$$n$$$ and $$$m$$$ ($$$0 \le n, m \le 1500$$$) — the number of red and blue points.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of a red point.

Each of the next $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of a blue point.

Over all test cases, the total number of red points is at most $$$1500$$$, and the total number of blue points is at most $$$1500$$$.

No three points in one test case, ignoring their colors, are collinear.

Output

For each test case, print one integer — the required number of valid good red subsets, modulo $$$2$$$.

Example
Input
4
3 1
0 0
4 0
0 4
1 1
4 1
0 0
4 0
0 4
1 1
1 2
4 1
0 0
5 0
6 4
-1 3
2 2
2 3
0 0
3 1
0 1
2 3
5 5
Output
1
0
1
0
Note

In the first test case, the only valid good subset is the set of all three red points, and its triangle contains the blue point.

In the second test case, the extra red point changes which red subsets are valid good. The number of valid good polygons containing an odd number of blue points is even, so the answer is $$$0$$$.

In the last test case, fewer than three red points are given, so there are no valid good subsets.