N sticks are randomly dropped on the 2D cartesian plane. You have to find the number of stick pairs that are in overlapping position. Two sticks are said to be in overlapping position if they have infinely many intersection points. A stick is defined by two dictinct points (x1, y1) and (x2, y2) which denote the end points of the stick.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing an integer N (1 ≤ N ≤ 105). Each of the next N lines contians four integers x1, y1, x2, y2 (-106 ≤ x1, y1, x2, y2 ≤ 106) forming a segment.
Output
For each case, print the case number and the number of stick pairs in overlapping position.
Sample
| Sample Input | Sample Output |
|---|---|
2 4 1 0 5 0 5 0 8 0 4 0 6 0 0 0 10 0 2 1 1 5 5 5 1 1 5 | Case 1: 5 Case 2: 0 |
Notes
Dataset is huge, use faster I/O methods.