Mahmud is playing a game with Ridwan. Mahmud is given N cartesian points by Ridwan. Mahmud can connect two points by drawing a line. Now there is a condition, he cannot draw a line which is already parallel to previously drawn lines. For each line drawn he will earn $D. Now Mahmud wants your help to find out what will be his maximum possible earning?
Input
Input starts with an integer T (0 < T ≤ 20), denoting the number of test cases.
Each test case starts with two Integers N (1 ≤ N ≤ 1000) and D (1 ≤ D ≤ 1000000000), where N denotes the number of points and D denotes the money you will earn for drawing a line. Then there will be N lines with two integers denoting the X and Y coordinates (-1000000000 ≤ Xi, Yi ≤ 1000000000). Each point will be distinct.
Output
For each test case, print the case number and Mahmud’s maximum possible earning.
Sample
| Input | Output |
|---|---|
1 4 1 -2 0 1 1 -1 1 0 0 | Case 1: 4 |
Mahmud can draw 4 lines with slope -1, 0, 1/3, and 1. | |
