## CVXPOLY - Convex Polygons

no tags

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274490/problem/B
 English Vietnamese

You are given n points in the 2-D cartesian coordinate system. You are to determine the number of convex polygons with 3 or more vertices which can be formed by choosing a subset of the given points. To make matters simple, the input obeys the following conditions:

(1) No 3 points in the input are collinear.

(2) No 2 points will have the same coordinates.

Since the result can be quite large, you are required to output ( result % 1234567 ) instead.

### Input

First line contains an integer T, the number of test cases. In each test case, first line contains n, the number of points in the corresponding test case, next n lines contain 2 space separated integers denoting the coordinate of ith point. Absolute value of the coordinates do not exceed 10000.

### Output

T lines each corresponding to the answer of corresponding test case.

### Example

```Input:
2
4
0 0
2 0
2 2
0 2
6
0 0
2 0
2 2
0 2
1 -1
1 3

Output:
5
42
```

### Constraints

```Input Set 1 : numberOfTestCases <= 100, 3 <= n <= 10 timeLimit: 5 seconds
Input Set 2 : numberOfTestCases <= 50, 3 <= n <= 100 timeLimit: 5 seconds
```

 Added by: Race with time Date: 2009-02-19 Time limit: 1.913s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: Code Craft 09