Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P147PROJ - ROUND 7J - Chiến hào

Gần 1 doanh trại quân đội, có 2 hệ thống hào, được mô phỏng bằng các đoạn thẳng trên mặt phẳng. Vào buổi đêm, khi hầu hết chiến sĩ đang ngủ say, 3 người bảo vệ thức để trông các
chiến hào. 2 người bảo vệ có thể nhìn thấy nhau nếu có 1 đường hào giữa 2 người, và không có người bảo vệ thứ 3 giữa 2 người. Vì lí do an ninh, các bảo vệ phải đứng ở vị trí mà mỗi người
có thể nhìn thấy 2 người còn lại. Có bao nhiêu cách xếp chỗ cho họ?

Input

Dòng đầu tiên ghi số bộ test (không quá 20). Mỗi bộ test gồm:  
* Dòng đầu tiên chứa số nguyên N( 1<= N<=20), là số lượng rãnh.  
* Mỗi N dòng tiếp theo mô tả 1 rãnh: 4 số nguyên X1, Y1, X2, Y2( tất cả nhỏ hơn hoặc bằng 1000), X1, Y1 là tọa độ 1 đầu của rãnh, X2, Y2 là tọa độ đầu còn lại.  
Các đường hào có thể chồng chéo và có chung điểm đầu, cuối.

Output

In ra số cách có thể xếp vị trí cho 3 người bảo vệ trên 1 dòng duy nhất.

Example

Input:
3 
6  
0 0 1 0  
0 0 0 1  
1 0 1 1  
0 1 1 1  
0 0 1 1  
1 0 0 1
4  
5 1 7 1  
1 1 5 1  
4 0 4 4  
7 0 3 4
3  
2 2 3 2  
3 2 3 3  
3 3 2 3 Output: 8
1
0

Được gửi lên bởi:adm
Ngày:2014-03-21
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

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