Polygon Count

Time limit2sMemory limit128 MB

Summary

Given up to 60 integer-coordinate segments drawn on paper, count how many simple closed polygons are formed, excluding faces from crossings and shapes touched by dangling extra edges.

Level: Hard8 of 10
Topics: Geometry, Graph, Union-find
Solved: No attempts yet

Problem

Given line segments whose endpoints have integer coordinates, draw all of them on paper. Compute how many polygons are formed using only those segments.

A polygon here means one simple closed figure made from at least three line segments. New regions that appear only because two polygons overlap or cross are not counted as polygons. Only closed figures made directly from the input segments are recognized.

Also, if a line segment that is not part of a closed figure is connected to that figure, the closed figure is not considered a polygon.

Input

The first line contains the number of line segments N, where 1 <= N <= 60.

Each of the next N lines describes one segment. A line contains, in order, the x-coordinate and y-coordinate of one endpoint, followed by the x-coordinate and y-coordinate of the other endpoint.

All coordinates are non-negative integers not greater than 10000.

Output

Print the number of polygons on the first line.

Examples1

Example 1

Input

23
70 160 100 200
60 60 70 160
100 120 130 130
90 70 140 110
70 160 70 110
70 110 120 90
70 160 120 140
120 140 120 90
90 70 100 120
130 130 140 110
60 60 110 140
110 140 160 80
150 160 160 80
120 170 160 80
120 140 150 140
140 90 160 120
160 120 170 130
170 130 190 120
200 80 220 50
200 80 230 110
220 90 230 110
220 90 230 80
220 50 230 80

Expected output