There are some(N <= 600) obstacles on the plant which are parallel to the X or Y axis. They may intersect but never overlap. Each obstacle have a cost (Ci <= 1000000) to cut through it once. Compute the minimum cost required to allow the people to travel anywhere in the plane. Cutting at any place of an obstacle except the intesection with another obstacle is valid.
Input
The first line is the number of test cases. Each test start with the number N. N line followed, each have five numbers. The first four is the coordinate of the obstacle's two endpoint. The last number is the Ci.
Output
Output one number for each line, which is the answer.
Sample Input
1
5
-10 10 10 10 1
-10 -10 10 -10 2
-5 -15 -5 15 3
0 -15 0 15 4
5 -15 5 15 5
Sample Output
2
