Elimination round completed

Tasks

Show one task per page / all tasks on one page

"D" Acute Triangles
Time limit 4 seconds
Memory limit 256 megabytes

Recently Moscow high school student Dmitri Zakharov set a new record on the number of points in d-dimensional space, such that all triangles with vertices in those points are acute.

Tanya wants to compete with Dmitri. Of course she is planning to use the computer. To make a good start, she decided to solve the following problem. Given n points on a plane, find the number of acute triangles that have vertices in those points. The triangle is acute if all of its angles are less than 90 degrees.

Input format

Input data contains multiple test cases. The first line of input contains integer t — the number of test cases (1 ≤ t ≤ 666).

Each test case is described by a line containing integer n (3 ≤ n ≤ 2000) — the number of points.

The following n lines contain two integers xi, yi each ( - 109 ≤ x, y ≤ 109) — coordinates of the points. It is guaranteed that in one test case all points are distinct.

The total number of points in all test cases of one input data doesn't exceed 2000.

Output format

For each test case output one line — the number of acute triangles with vertices in the given points.

Examples
Input data
2
5
1 1
2 2
3 3
4 1
6 4
5
0 0
3 1
5 1
5 -1
1 3
Output data
3
4
 

Send solution

Upload Maximal size is 256kb

Log in

VK Facebook

Forgot password?

Registration

The instruction for password recovery
has been sent to your email