파이 나누기

프란스는 생일을 맞았습니다. 그는 고급 제과점에서 서로 다른 종류의 맛있는 파이 두 판을 샀고, 각 파이를 여러 조각으로 잘랐습니다. 티타임에 동료들을 초대해 파이를 나눠 먹었지만, 잔치가 끝난 뒤에도 조각이 남았습니다. 정확히 $2N$개, 즉 각 파이에서 $N$조각씩 남았고 $N$은 짝수입니다. 프란스는 남은 조각을 모두 집으로 가져가고 싶지 않아, 파이를 좋아하는 동료 한 명과 나누기로 했습니다.

남은 조각들은 탁자 위에 흩어져 있습니다. 프란스는 이것을 하나의 직선으로 둘로 나누려 합니다. 탁자 위에 끈을 팽팽하게 직선으로 놓고, 끈의 한쪽에 있는 조각은 프란스가, 다른 쪽에 있는 조각은 동료가 가져갑니다. 단, 조건이 하나 있습니다. 두 사람 각각이 첫 번째 파이 조각을 정확히 $N/2$개, 두 번째 파이 조각을 정확히 $N/2$개씩 가져가야 합니다.

이런 끈 나누기가 가능한지, 가능하다면 몇 가지 방법이 있는지는 $2N$개 조각의 위치에 따라 달라집니다. 두 나눔이 조각들을 같은 두 묶음으로 가르면 같은 방법으로 봅니다. 즉, 어느 묶음이 프란스의 것인지는 구분하지 않습니다. 예를 들어 $N = 2$일 때, 네 조각의 배치에 따라 유효한 나눔이 두 가지인 경우도 있고 한 가지뿐인 경우도 있습니다.

문제를 단순하게 하기 위해, 어떤 세 조각도 한 직선 위에 있지 않다고 가정합니다. 특히 두 조각이 같은 위치에 있는 경우도 없습니다. 또한 각 조각은 무한히 작은 점으로 간주합니다.

첫 줄에는 테스트 케이스의 개수를 나타내는 정수 하나가 주어집니다. 각 테스트 케이스는 다음 형식을 따릅니다.

• 짝수 정수 $N$이 한 줄에 주어집니다 ($2 \le N \le 1000$).
• $N$개의 줄에 각각 두 정수 $x$, $y$가 주어집니다 ($-10000 \le x, y \le 10000$). 첫 번째 파이 조각의 좌표입니다.
• $N$개의 줄에 각각 두 정수 $x$, $y$가 주어집니다 ($-10000 \le x, y \le 10000$). 두 번째 파이 조각의 좌표입니다.

한 줄의 두 정수는 공백 하나로 구분됩니다.

각 테스트 케이스마다, 하나의 직선 끈으로 $2N$개의 조각을 두 묶음으로 나누되 끈의 양쪽에 각각 첫 번째 파이 $N/2$조각과 두 번째 파이 $N/2$조각이 오도록 하는 방법의 수를 한 줄에 정수 하나로 출력합니다.