Acme Counting Machines has hired you as a consultant to finish their TCM-2000 project. The TCM- 2000 is a machine for counting triangles in pictures by means of a video camera attached to a computer. They have already done the easy part of preprocessing the picture to extract the edges and convert the image into a list of segments. Your job is to write a program to count all the non-overlapping triangles defined by those segments. A triangle consists of exactly three segments. Your program will receive a list of non-intersecting and non-overlapping segments and it has to return the number of non-overlapping triangles in the figure. For example, given the following figure: Your program would receive the following list of segments: AB, AD, AF, BC, BF, CD, CE, CF, DE and DF. Then, it will have to count the 5 triangles present in the figure, namely: ABF, ADF, BCF, CDE and CDF. Input The input format is as follows: An integer in a single line which says the number of figures that your program will have to process. Then, for each figure there will be: • An integer in a single line which says the number of segments in that figure. • A line for each segment, with four numbers each line. The first two numbers are the coordinates of one of the end points of the segment, and the last two numbers are the coordinates of the second end point. The numbers may be either integers or floating point numbers with at most one figure after the decimal point. Output The output consists of one line for each case, with a single integer number each: the number of triangles found. Sample Input 1 10 0001 0 0 0.5 0.5 0010 0 1 0.5 0.5 0 1 0.5 1.5 0111 0.5 0.5 1 0 0.5 0.5 1 1 0.5 1.5 1 1 1011
2/2 Sample Output 5