인술

인술은 수수께끼의 일본 암살자인 닌자의 무술이다. 인술을 처음 수련하는 초보자로서, 여러분의 첫 과제는 그래플링 훅의 사용법을 익히는 것이다.

그래플링 훅은 갈고리를 (매우 튼튼하고 매우 가는) 밧줄에 묶은 첨단 장치이다. 그래플링 훅을 올바르게 사용하려면 갈고리를 표적에 던지고 걸리기를 바라야 한다.

이번에는 걸렸다! 이제 여러분은 (0, 0)에 있는 표적에 걸려 있다. 밧줄은 왼쪽으로 뻗어 있고 여러분은 그 끝에 있으며, 뛰어내리면 표적 주위를 반시계 방향으로 흔들리기 시작한다. (0, 0)의 오른쪽 위쪽에는 다른 표적들이 있으며, 그 위치는 ($x_{i}$, $y_{i}$))이고 $x_{i}$ ≥ 0 및 $y_{i}$ ≥ 0이다. 밧줄의 내부 지점(양 끝점이 아닌 지점)이 하나 이상의 표적과 접촉하면, 밧줄은 움직이는 끝에 가장 가까운 표적을 둘러싸며 꺾인다. 시작 속도는 무시한다. 여러분은 닌자이므로 속도가 충분히 빨라서, 하나의 표적만을 중심으로 회전하게 될 때까지 계속 표적을 둘러싸며 꺾이게 된다.

현재 밧줄의 길이는 R이지만, 흔들리기 시작하기 전에 더 짧은 임의의 길이 r(정수가 아닌 값도 포함)로 잘라도 된다. 따라서 (-r, 0)에서 시작하여 (0, -r)을 향해 아래쪽으로 반시계 방향으로 흔들린다.

한 번 흔들어서 밧줄을 최대 몇 번 꺾을 수 있는가? 밧줄이 표적에 닿은 뒤 그 표적을 중심으로 영이 아닌 각도만큼 회전하면 한 번 꺾인 것으로 본다. 꺾인 지점을 제외하면 밧줄은 항상 완벽한 직선을 유지한다(이 역시 여러분이 닌자이므로 가능하다).

예제

위 예제에는 6개의 점이 있다.

• (0, 0),

• (3, 1),

• (12, 4),

• (14, 5),

• (13, 7), 그리고

• (7, 10).

길이가 24인 밧줄이 있다. 밧줄을 자르지 않으면 점 (12, 4)을 둘러싸며 꺾인 다음, 점 (14, 5)을 둘러싸며 꺾이고, 이어서 점 (13, 7)을 둘러싸며 꺾인 뒤, 마지막에는 약 0.1705 단위 길이의 밧줄이 남은 채 점 (7, 10)을 중심으로 계속 돌게 된다. 이는 총 4번 꺾이는 것에 해당한다. 점 (3, 1)에 닿기는 하지만, 이 점은 점 (0, 0) 및 (12, 4)과 일직선상에 있으므로 꺾임에 포함되지 않는다.

그러나 밧줄을 0.18 단위만큼 자르면 점 (7, 10)에 닿을 만큼 길지 않으므로, 대신 다음 경로를 따른다.

(0, 0)--(12, 4)--(14, 5)--(13, 7)--(12, 4)--(14, 5)

그리고 약 1.3004 단위 길이의 밧줄이 남은 채 점 (14, 5)을 중심으로 계속 돌게 된다. 이 경로에서는 총 5번 꺾이며, 이는 최적해이다.

아래 예제 입력의 케이스 #1이 이 예제를 나타낸다.

제한

시간 제한: 테스트 세트당 60초. 메모리 제한: 1GB. 1 ≤ T ≤ 100 모든 표적의 좌표는 정수이다. 모든 표적은 서로 다른 위치에 있다. 가장 먼저 나열된 표적은 (0, 0)에 있다. 최적해를 만들며, 길이가 r - 0.999999인 밧줄도 같은 해(동일한 꺾임 순서)를 만드는 성질을 갖는 r의 값이 적어도 하나 존재한다.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ N ≤ 10 1 ≤ R ≤ 1,000 0 ≤ $x_{i}$ ≤ 1,000 0 ≤ $y_{i}$ ≤ 1,000

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ N ≤ 1,000 1 ≤ R ≤ $10^{9}$ 0 ≤ $x_{i}$ ≤ $10^{9}$ 0 ≤ $y_{i}$ ≤ $10^{9}$

입력은 이어지는 테스트 케이스의 수 T가 적힌 한 줄로 시작한다. 각 테스트 케이스는 한 줄에 함께 주어지는 두 정수 N과 R로 시작한다. 다음 N개의 줄에는 각각 표적의 좌표인 두 정수 $x_{i}$와 $y_{i}$가 주어지며, (0, 0)에 있는 표적부터 시작한다.

각 테스트 케이스마다 "Case #C: k" 형식의 한 줄을 출력한다. 여기서 C는 1를 기준으로 하는 케이스 번호이고, k는 한 번 흔들어서 밧줄에 만들 수 있는 최대 꺾임 횟수이다.