Problem

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.

Input

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

Output

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.

Limits

Time limit: 30 5 seconds per test set.

Memory limit: 1 GB.

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 (3 Points)

1 ≤ n ≤ 15

Large dataset (25 Points)

1 ≤ n ≤ 500

Sample

1
5
0 1 7 10
0 -1 7 10
5 0 1 -15
10 0 6 10
15 1 2 -20

Case #1: 5