Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3016
Cut

Time Limit: 5 Seconds      Memory Limit: 65536 KB

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