Migrated from Lutece 1495 B

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There are $N$ bombs needing exploding.

Each bomb has three attributes: exploding radius $r_i$, position $(x_i,y_i)$ and lighting-cost $c_i$ which means you need to pay $c_i$ cost making it explode.

If a un-lighting bomb is in or on the border the exploding area of another exploding one, the un-lighting bomb also will explode.

Now you know the attributes of all bombs, please use the minimum cost to explode all bombs.

Input

First line contains an integer $T$ ($1\le T\le 20$), which indicates the number of test cases.

Every test case begins with an integers $N$ ($1\le N\le 1000$), which indicates the numbers of bombs.

In the following $N$ lines, the $i$-th line contains four intergers $x_i$, $y_i$, $r_i$ and $c_i$ ($-10^8\le x_i,y_i,r_i\le 10^8,1\le c_i\le 10^4$), indicating the coordinate of $i$-th bomb is $(x_i,y_i)$, exploding radius is $r_i$ and lighting-cost is $c_i$.

Output

For every test case, you should output Case #x: y, where x indicates the case number and counts from $1$ and y is the minimum cost.

Samples

1
5
0 0 1 5
1 1 1 6
0 1 1 7
3 0 2 10
5 0 1 4

Case #1: 15

Resources

第二届中国大学生程序设计竞赛 杭州站（CCPC 2016 Hangzhou Site）