Description
A conservation group found a way to scan the cross-section of elephant tusks like the one shown on the left. The scanned image of a tusk is a collection of bright spots, which can be treated as a set of points on the plane, where no three points form a straight line. The group made a database of many tusks and hope that the database can help in tracking illegal ivory trade.
To facilitate retrieval from the database, it is desirable to have a feature representation that remains unchanged even if a scanned image is translated or rotated. They decided to use the number of k -sets to represent a set of points, which is defined below.
Consider a set P of n points in the plane, where no three points form a straight line. Any line in the plane that does not contain a point in P will split the set into two sets X , Y , where X contains points on one side of the line and Y contains points on the other side. If the number of points in X is k , then we call the collection {X, Y} a k -set in P . Note that {X, Y} = {Y, X} , and thus a k -set is also an (n - k) -set. Given a set P and k , your task is to compute the number of different k -sets in P .
Input
The input consists of a line containing the number c of datasets, followed by c datasets, followed by a line containing the number `0'.
The first line of each dataset contains two integers, separated by a blank. The first integer gives the number n of points in P , and the second integer gives k , where (0 < k < n ≤ 2000) . The following n lines of each dataset each contains two non-negative integers, indicating the x and y -coordinates of the corresponding point. The x and y -coordinates range from 0 to 10000.
Output
The output consists of one line for each dataset. The c -th line contains the number of k -sets for dataset c .
Note: This dataset and the lines that form its 2-sets are shown in Figure 3.