CVXPOLY - Convex Polygons

no tags 

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/cvxpoly


Cho n điểm trong hệ tọa độ Đề các 2-D. Bạn phải tính số lượng đa giác lồi có lớn hơn hoặc bằng 3 đỉnh mà có thể tạo thành bằng cách chọn một tập hợp con trong tập hợp các điểm đã cho. Để đơn giản, dữ liệu vào đảm bảo các điều kiện sau:

    (1) Không có 3 điểm bất kỳ nào thẳng hàng.

    (2) Không có 2 điểm nào có cùng tọa độ.

Do kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho 1234567

Input

Dòng đầu chứa số nguyên T, số lượng test. Trong mỗi test: dòng đầu chứa n là số lượng điểm của test đó; n dòng tiếp theo, dòng thứ i chứa 2 số nguyên là tọa độ của điểm thứ i. Trị tuyệt đối của các tọa độ không quá 10000.

Output

T dòng, mỗi dòng ghi đáp án cho test tương ứng.

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 : T <= 100, 3 <= n <= 10 timeLimit: 5s  
Input Set 2 : T <= 50, 3 <= n <= 100 timeLimit: 5s 


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