Gần một căn cứ quân sự có một hệ thống hào hầm, được mô hình hóa như các đoạn thẳng trên một mặt phẳng. Vào ban đêm, khi hầu hết binh sĩ đều ngủ say, ba người bảo vệ đứng canh hào hầm. Hai người bảo vệ có thể nhìn thấy nhau nếu có một hào hầm (hoặc một dãy hào hầm) dọc theo toàn bộ đoạn thẳng giữa họ và không có người bảo vệ thứ ba trên đoạn thẳng đó. Vì lý do an ninh, các người bảo vệ phải được đặt sao cho mỗi người nhìn thấy hai người kia. Hỏi có bao nhiêu cách để họ được đặt?

Input

• Dòng đầu chứa số nguyên ~N~ ~(1 \leq N \leq 20)~, số lượng hào hầm.
• Mỗi dòng trong ~N~ dòng sau chứa mô tả của mỗi hào hầm: bốn số nguyên ~X1, Y1, X2, Y2~ ~(X1, Y1, X2, Y2 \leq 1000)~. ~X1, Y1~ là tọa độ của một đầu, ~X2, Y2~ là tọa độ của đầu kia.

Các hào hầm có thể chổng lên nhau vào chung điểm cuối.

Output

In ra số cách đặt các người bảo vệ.

Sample Input 1

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

Sample Output 1

8

Sample Input 2

4
5 1 7 1
1 1 5 1
4 0 4 4
7 0 3 4

Sample Output 2

1

Sample Input 3

3
2 2 3 2
3 2 3 3 
3 3 2 3

Sample Output 3

0