E. Tangled
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ distinct points on a plane. The coordinates of the $$$i$$$-th point are $$$(x_i, y_i)$$$.

Your task is to calculate the number of pairs of indices $$$(i, j)$$$ such that $$$1 \le i \lt j \le n$$$ and the line segment connecting points $$$(x_i, y_i)$$$ and $$$(x_j, y_j)$$$ intersects the line segment connecting points $$$(y_i, x_i)$$$ and $$$(y_j, x_j)$$$.

Two line segments are considered intersecting if they have at least one common point.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of points.

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

It is guaranteed that all points in a test case are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print a single integer — the number of pairs of indices $$$(i, j)$$$ satisfying the required condition.

Example
Input
1
3
1 3
3 1
5 4
Output
2
Note

In the first test case, all $$$3$$$ pairs of indices are listed below:

  • For pair $$$(1, 2)$$$, the segment connecting $$$(1, 3)$$$ and $$$(3, 1)$$$ is the same as the segment connecting $$$(3, 1)$$$ and $$$(1, 3)$$$, so they intersect.
  • For pair $$$(1, 3)$$$, the segment connecting $$$(1, 3)$$$ and $$$(5, 4)$$$ intersects the segment connecting $$$(3, 1)$$$ and $$$(4, 5)$$$.
  • For pair $$$(2, 3)$$$, the segment connecting $$$(3, 1)$$$ and $$$(5, 4)$$$ does not intersect the segment connecting $$$(1, 3)$$$ and $$$(4, 5)$$$.

The valid pairs are $$$(1, 2)$$$ and $$$(1, 3)$$$. Therefore, the answer is $$$2$$$.