와이파이 탑 (작은 입력)

무선 통신 탑 $n$개로 이루어진 네트워크가 있다. 탑마다 도달 거리가 정해져 있고, 두 탑 사이의 거리가 보내는 탑의 도달 거리 이하이면 그 탑으로 자료를 보낼 수 있다.

지금은 모든 탑이 구형 프로토콜 A를 쓴다. 대역폭이 더 나은 신형 프로토콜 B가 나와서, 일부 탑을 프로토콜 B로 바꾸려고 한다.

제약이 하나 있다. 탑 $T$가 프로토콜 B를 쓰면, $T$의 도달 거리 안에 있는 모든 탑도 프로토콜 B를 써야 한다. 그래야 $T$가 보낸 자료를 해석할 수 있다. 반대 방향은 상관없다. 프로토콜 B를 쓰는 탑은 프로토콜 A를 쓰는 탑이 보낸 자료를 그대로 받을 수 있다.

탑을 바꾸면 이득이 생기지만 설치 비용도 든다. 그래서 탑마다 바꿨을 때의 가치를 나타내는 점수가 있고, 이 점수는 양수일 수도 있고 음수일 수도 있다. 바꿀 탑의 집합을 골라서 바꾼 탑의 점수 합을 최대로 만들어라. 아무 탑도 바꾸지 않는 선택도 가능하며, 이때 합은 $0$이다.

거리는 유클리드 거리다. 탑은 항상 자기 자신의 도달 거리 안에 있으므로, 제약의 이 부분이 선택을 막지는 않는다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 탑의 개수 $n$이 주어진다. 이어지는 $n$개 줄에는 정수 네 개 $x$, $y$, $r$, $s$가 주어진다. 좌표 $(x, y)$에 있는 탑의 도달 거리가 $r$이고, 프로토콜 B로 바꿨을 때의 점수가 $s$라는 뜻이다.

제한:

• $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$
• 좌표가 같은 탑은 없다.

각 테스트 케이스마다 한 줄을 출력한다.

Case #X: score

$X$는 1부터 시작하는 테스트 케이스 번호이고, score는 얻을 수 있는 최대 점수 합이다.