Wi-Fi Towers (Small)

A wireless network has $n$ towers. Every tower has a range, and it can send data to another tower when the distance between the two towers is at most the range of the sending tower.

All towers currently run the old protocol A. A new protocol B gives better bandwidth, so you plan to upgrade some towers to protocol B.

One restriction applies. If tower $T$ runs protocol B, then every tower inside the range of $T$ must run protocol B as well, so that it can read the data $T$ sends. The other direction is free: a tower running protocol B can still receive data from a tower running protocol A.

An upgrade brings a benefit and also costs something to install, so every tower carries a score that may be positive or negative. Pick the set of towers to upgrade so that the sum of the scores of the upgraded towers is as large as possible. Upgrading no tower at all is a valid choice, and its total is $0$.

Distances are Euclidean. A tower always lies inside its own range, so that part of the restriction never blocks a choice.

The first line contains the number of test cases, $T$. Each test case starts with a line holding the number of towers, $n$. Each of the next $n$ lines contains four integers $x$, $y$, $r$, $s$, describing a tower at coordinates $(x, y)$ with range $r$ and score $s$ for upgrading it to protocol B.

Constraints:

• $1 \le T \le 55$
• $1 \le n \le 15$
• $-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:

Case #X: score

$X$ is the number of the test case, starting from 1, and score is the largest total score you can reach.