In the country of Graphland, there are many cities but no roads. The federal government wants to change this situation and plans to build roads and railroads such that all the cities in the country are connected through this new transportation system. To make the new system more efficient, Graphland will build only roads between cities within the same state and will use railroads to connect cities that are in different states. For the purposes of this problem, consider that if the distance between any two cities is at most r then they are in the same state. To minimize the costs of building the roads and railroads, the government also wants to build only the minimum necessary extension of roads and railroads such that there is a path between any pair of cities in the entire country. You’ve been hired to determine what’s the optimum transportation network system that Graphland must build. The first line of the input contains the number of test cases that follow. On the first line of each test case, there will be two integers, n (1 ≤ n ≤ 1000), the number of cities that comprise Graphland, and r (0 ≤ r ≤ 40000), the threshold value to determine if two cities are in the same state. On the following n lines, there will be a list of x − y (−10000 ≤ x, y ≤ 10000) integer coordinates in the plan for each city in Graphland. Your program must output the number of states in Graphland and the minimum extension (rounded to the nearest integer) of both roads and railroads that must be built to satisfy the conditions of the project. Input The first line of input gives the number of cases, T (1 ≤ T ≤ 20). T test cases follow. On the first line of each test case, there will be two integers, n (1 ≤ n ≤ 1000), the number of cities that comprise Graphland, and r (0 ≤ r ≤ 40000), the threshold value to determine if two cities are in the same state. On the following n lines, there will be a list of x − y (−10000 ≤ x, y ≤ 10000) integer coordinates in the plan for each city in Graphland. Output The output is comprised of one line for each input data set. The line identifies the data set with a number (starting from one and incrementing at each new data set), followed by the number of states in Graphland and the minimum extension (rounded to the nearest integer) of both roads and railroads that must be built to satisfy the conditions of the project. Note: Notice that, by the definition, if A and B are in the same state, and B and C are in the same state, then A and C are also in the same state. Sample Input 3 3 100 00 10 20 31 00 100 0 200 0 4 20
2/2 00 40 30 30 30 10 10 Sample Output Case #1: 1 2 0 Case #2: 3 0 200 Case #3: 2 24 28