Wi-Fi Tower Upgrade

You are given a network of wireless towers. Each tower has a range and sends data to another tower whenever the distance to it is at most the sending tower's range.

Every tower currently runs the old protocol A. A new protocol B with better bandwidth is available, and you want to upgrade some of the towers to B.

One restriction applies. If a tower $T$ runs the new protocol B, every tower within $T$'s range must run B as well, so that they understand the data $T$ sends. The reverse is not required. A tower running the new protocol B may still receive data from a tower running the old protocol A.

An upgrade brings a benefit and also costs money to install. Each tower therefore carries one score, the value of upgrading it, and that score is positive or negative. Choose the set of towers to upgrade so that the total score of the upgraded towers is as large as possible. You may upgrade no tower at all, in which case the total is 0.

The first line contains the number of test cases $T$.

Each test case starts with a line containing the number of towers $n$. Each of the next $n$ lines contains four integers $x$, $y$, $r$, $s$ separated by spaces: a tower at coordinates $(x, y)$ with range $r$ and score $s$, the value of upgrading it to the new protocol.

Distances between towers are Euclidean. Tower $A$ sends data to tower $B$ when the distance from $A$ to $B$ is at most $A$'s range.

Limits

• $1 \le T \le 55$
• $1 \le n \le 500$
• $-10000 \le x, y \le 10000$
• $1 \le r \le 20000$
• $-1000 \le s \le 1000$
• No two towers share the same coordinates.

For each test case, print one line in this format:

Case #X: score

Here $X$ is the test case number starting from 1, and score is the total score of the best choice.