Description
Wireless communication has become a more and more popular issue in the EECS studies, even though almost all commercial applications are based on a “wired” backbone infrastructure. As the best engineer of the company Hexagonal Electrical eXample (HEX corp.), you are to solve the wire routing problem for the new wireless service of the company.
The HEX corp. is building a new wireless service in a city. As what we told you, the HEX corp. has decided where to build the Access Point (AP) for wireless communication. The APs are distributed depending on the population, geography, and some other issues, and then use the cable to connect them together. In order to keep the maintenance more easily, HEX corp. wishes to route the cables by the streets in the city. Except two ends of cable, any other parts on the cable are insulated. Therefore, two cables on the same street would not affect each other and not be merged into one cable.
The layout of streets in city is very special. There are 3 types of street, which are called type 1, type 2, and type 3. Within each type, streets are parallel. The distances between every 2 parallel streets are the same, and there must be 3 streets cross each intersection.
Any APs are built on the intersections of streets. Assume the length of each street segment is 1; the total cost of the routing is the sum of lengths of cables used. Any APs can be connected indirectly, i.e. if there is a cable connecting AP1 and AP2, and another cable connects AP2 and AP3, then AP1 and AP3 are connected.
You are to determine what is the minimum cost required to connect all APs, by telling the HEX corp. what is the minimum sum of lengths of cables required.
Input
There are several cases in the input. There is an integer T, T ≤ 100, in first line of input, which indicates the number of cases.
For each case following, the first line contains a number N, N ≤ 1000, which indicates the number of APs.
There are N lines following. For the ith line of these lines, there are 3 integers, S(i,1), S(i,2), and S(i,3), which indicate the streets of type 1, type 2, and type 3 which cross the intersection. All these numbers are between 1 and 1000.
Output
For each case, output one line with one integer to indicate the minimum cost of network.