Pulse Nova

Mr.Panda는 타워 디펜스 게임 Watcher of Samsara를 하고 있다. 게임을 시작할 때 모든 플레이어는 게임 시스템이 무작위로 생성한 영웅 풀에서 첫 번째 영웅을 자유롭게 고를 수 있다. Mr.Panda는 항상 Leshrac을 고르는데, 이 캐릭터의 궁극기 Pulse Nova 때문이다.

Pulse Nova는 Leshrac 주변에 1초에 한 번씩 피해 에너지의 파동을 내보내, 근처의 모든 적 유닛에게 피해를 준다. 이 스킬을 보고 Mr.Panda는 기하 문제를 떠올렸다.

2차원 평면 위에 $n$개의 직선이 있다. $i$번째 직선은 정수 좌표인 두 점 $P_i$, $Q_i$를 지난다. 평면 위에 반지름이 정확히 $R$인 원을 하나 놓아야 한다. 주어진 각 직선에 대해, 그 직선의 일부 선분이 원 안에 들어갈 수 있다. 원 안에 들어가는 모든 선분의 길이 합이 최대가 되도록 원의 위치를 구하라.

첫 줄에는 테스트 케이스의 개수 $T$ ($1 \le T \le 100$)가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 직선의 개수 $n$ ($1 \le n \le 50$)과 원의 반지름 $R$ ($1 \le R \le 3000$)이 정수로 주어진다.

이후 $n$개의 줄에 각각 정수 네 개가 주어진다. $i$번째 줄의 처음 두 정수는 점 $P_i$의 좌표이고, 나머지 두 정수는 점 $Q_i$의 좌표이다. $P_i \ne Q_i$이고, 모든 좌표의 절댓값은 1000 이하이다.

모든 테스트 케이스의 $n$을 합하면 100 이하이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 원 안에 들어가는 길이의 최대 합이다. 절대 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정한다.

첫 번째 예시에서 원의 중심을 $(1, 1)$에 두면 원 안에 들어가는 길이의 합은 8이 된다.

두 번째 예시에서 원의 중심을 $(0, 1)$에 두면 원 안에 들어가는 길이의 합은 $12 + 8\sqrt{2}$가 된다.