CVXPOLY - Convex Polygons

no tags 

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 

hide comments
Race with time: 2009-04-14 12:17:32

Time limit has been updated.

Ajay Somani: 2009-04-14 12:17:32

It seems the problem author has taken the time limit from the original solution and released test data. But the judge server at codecraft was faster than the judging machines at SPOJ, hence the strict time limit.

[Trichromatic] XilinX: 2012-11-09 11:19:23

Almost the same as problem BOYSCOUT - with a very strict time limit.


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