Pie Division

Frans is celebrating his birthday. At an exclusive bakery he bought two delicious pies of different types. He cuts each pie into several pieces and, at coffee time, invites his colleagues over for a slice. After the celebration some pieces are left over — in fact exactly $2N$ pieces remain: $N$ pieces of each pie, and $N$ happens to be even. Frans does not want to take all of them home, so he decides to share them with a colleague who is also fond of pie.

The leftover pieces are scattered across the table, and Frans wonders how to split them into two. A simple way is to stretch a cord in a straight line over the table: the pieces on one side of the cord are for Frans, and the pieces on the other side are for his colleague. There is, however, a condition — each of them must take home exactly $N/2$ pieces of the first pie and $N/2$ pieces of the second pie.

Is this possible with the cord trick, and if so, in how many ways? Naturally, this depends on where the $2N$ pieces lie. Two divisions are regarded as the same when they separate the pieces into the same two groups; it does not matter which group ends up being Frans's. For example, when $N = 2$ some arrangements of the four pieces admit two valid divisions, while others admit only one.

To keep things simple, assume that no three pieces lie on one straight line (in particular, no two pieces share the same position), and treat every piece as an infinitely small point.

The first line contains a single integer: the number of test cases that follow. Each test case has the following format:

• One line with an even integer $N$, where $2 \le N \le 1000$.
• $N$ lines, each with two integers $x$ and $y$, where $-10000 \le x, y \le 10000$: the coordinates of a piece of the first pie.
• $N$ lines, each with two integers $x$ and $y$, where $-10000 \le x, y \le 10000$: the coordinates of a piece of the second pie.

The two integers on a line are separated by a single space.

For each test case, print a single line with one integer: the number of ways to split the $2N$ pieces into two groups with a single straight cord so that each side of the cord holds $N/2$ pieces of the first pie and $N/2$ pieces of the second pie.