인술 (라지)

인술은 일본의 은밀한 암살자인 닌자가 익히는 무술이다. 인술에 입문한 당신의 첫 과제는 갈고리 밧줄을 다루는 것이다.

갈고리 밧줄은 아주 튼튼하고 아주 얇은 줄에 갈고리를 묶은 도구다. 갈고리를 표적에 던져서 걸리기를 기대하는 방식으로 쓴다. 이번에는 걸렸다. 지금 갈고리는 $(0, 0)$에 있는 표적에 걸려 있고, 줄은 왼쪽으로 뻗어 있으며, 당신은 그 끝을 잡고 있다. 그래서 뛰어내리면 그 표적을 중심으로 반시계 방향으로 돌기 시작한다. 즉 $(-r, 0)$에서 출발해 $(0, -r)$ 쪽으로 내려간다.

나머지 표적은 모두 $(0, 0)$의 오른쪽과 위쪽, 곧 $x_i \ge 0$이고 $y_i \ge 0$인 $(x_i, y_i)$에 있다. 줄의 양 끝이 아닌 내부의 점이 표적 하나 이상에 닿으면, 줄은 움직이는 끝에 가장 가까운 표적을 중심으로 꺾인다. 처음 속도는 무시한다. 당신은 닌자여서 속도가 충분히 빠르고, 표적 하나만을 중심으로 돌게 될 때까지 계속 표적을 감으며 꺾인다.

줄의 길이는 $R$이지만, 돌기 시작하기 전에 이보다 짧은 임의의 길이 $r$로 잘라낼 수 있다. $r$은 정수가 아니어도 된다. 꺾임은 줄이 표적에 닿은 뒤 그 표적을 중심으로 0이 아닌 각도만큼 회전할 때 한 번 생긴다. 꺾이는 지점을 빼면 줄은 완벽하게 곧게 유지된다. 이것도 당신이 닌자여서 가능하다.

한 번의 스윙으로 줄에 만들 수 있는 꺾임의 최대 개수를 출력한다.

예를 들어 표적이 여섯 개 있다고 하자.

• $(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번이고, 이것이 최적이다.

이 배치가 첫 번째 예제의 첫 케이스다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $R$이 주어진다. 이어지는 $N$개의 줄에는 표적 하나의 좌표 $x_i$와 $y_i$가 두 정수로 주어진다. 가장 먼저 주어지는 표적이 $(0, 0)$에 있는 표적이다.

각 테스트 케이스마다 Case #C: k 형식으로 한 줄을 출력한다. $C$는 1부터 시작하는 케이스 번호이고, $k$는 한 번의 스윙으로 줄에 만들 수 있는 꺾임의 최대 개수다.

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $1 \le R \le 10^9$
• $0 \le x_i \le 10^9$, $0 \le y_i \le 10^9$
• 모든 좌표는 정수이고, 표적의 위치는 모두 다르다.
• 가장 먼저 주어지는 표적은 $(0, 0)$에 있다.
• 최적의 답을 주는 길이 $r$ 가운데, 길이가 $r - 0.999999$일 때도 같은 꺾임 순서로 같은 답을 주는 값이 적어도 하나 있다.