Mr. Panda lives in Pandaland. There are many cities in Pandaland. Each city can be treated as a point on a 2D plane. Different cities are located in different locations.

There are also M bidirectional roads connecting those cities. There is no intersection between two distinct roads except their endpoints. Besides, each road has a cost w.

One day, Mr. Panda wants to find a simple cycle with minmal cost in the Pandaland. To clarify, a simple cycle is a path which starts and ends on the same city and visits each road at most once.

The cost of a cycle is the sum of the costs of all the roads it contains.

There are also M bidirectional roads connecting those cities. There is no intersection between two distinct roads except their endpoints. Besides, each road has a cost w.

One day, Mr. Panda wants to find a simple cycle with minmal cost in the Pandaland. To clarify, a simple cycle is a path which starts and ends on the same city and visits each road at most once.

The cost of a cycle is the sum of the costs of all the roads it contains.

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case begins with an integer M.

Following M lines discribes roads in Pandaland.

Each line has 5 integers $x_1, y_1, x_2, y_2,$ w, representing there is a road with cost w connecting the cities on $(x_1, y_1)$ and $(x_2, y_2).$

Each test case begins with an integer M.

Following M lines discribes roads in Pandaland.

Each line has 5 integers $x_1, y_1, x_2, y_2,$ w, representing there is a road with cost w connecting the cities on $(x_1, y_1)$ and $(x_2, y_2).$

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the cost Mr. Panda wants to know.

If there is no cycles in the map, y is 0.

## limits

$\bullet 1 ≤ T ≤ 50.$

$\bullet 1 ≤ m ≤ 4000.$

$\bullet -10000 ≤ x_i , y_i ≤ 10000.$

$\bullet 1 ≤ w ≤ 10^5.$

If there is no cycles in the map, y is 0.

$\bullet 1 ≤ T ≤ 50.$

$\bullet 1 ≤ m ≤ 4000.$

$\bullet -10000 ≤ x_i , y_i ≤ 10000.$

$\bullet 1 ≤ w ≤ 10^5.$

提交代码