CVXPOLY - Convex Polygons

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 

Được gửi lên bởi:Race with time
Ngày:2009-02-19
Thời gian chạy:1.913s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Code Craft 09

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.