You are given a network of wireless towers. Each tower has a range and can send data to neighboring towers as long as the distance is less than or equal to the sending tower's range.

The towers are using an old communication protocol A, but there is a new, better protocol B available. We are thinking about upgrading some towers to send data using protocol B to achieve better bandwidth.

There is one important restriction: if a tower T is using the new protocol B, every tower within T's range must also be running protocol B, so that they can understand the data sent from T. The reverse is not necessary — towers running the new protocol B can be sent data from towers using the old protocol A.

Your task is to select the best set of towers to upgrade from protocol A to protocol B. There is some benefit to upgrading a tower, but there are also installation costs. So each tower will have a score, which can be positive or negative, which is the value of upgrading the tower. Choose the set of towers to upgrade in such a way that the total score of the upgraded towers is maximized.


The first line contains the number of test cases, T. Each test case starts with the number of towers, n. The following n lines each contain 4 integers: x, y, r, s. They describe a tower at coordinates x, y having a range of r and a score (value of updating to the new protocol) of s


For each test case, output:
Case #X: score
where X is the test case number, starting from 1, and score is the total score for the best choice of towers.


1 ≤ T ≤ 55
-10 000 ≤ x, y ≤ 10 000
1 ≤ r ≤ 20 000
-1000 ≤ s ≤ 1000

No two towers will have the same coordinates.

Small dataset

1 ≤ n ≤ 15

Large dataset

1 ≤ n ≤ 500



0 1 7 10
0 -1 7 10
5 0 1 -15
10 0 6 10
15 1 2 -20
Case #1: 5

Points Correct Attempted
3pt 22 22
25pt 9 12

Subscribe to our newsletter

Join our monthly newsletter and never miss out on new stories and promotions.