인술 (작은 입력)

인술은 일본의 암살자 닌자가 쓰는 무술이다. 인술을 배우기 시작한 당신에게 주어진 첫 과제는 갈고리 밧줄을 능숙하게 다루는 것이다.

갈고리 밧줄은 아주 튼튼하고 아주 가는 밧줄에 갈고리를 묶은 도구다. 갈고리를 목표물에 던져 걸리기를 바라면서 쓴다.

이번에는 걸렸다. 지금 당신은 $(0, 0)$에 있는 목표물에 갈고리로 걸려 있다. 밧줄은 왼쪽으로 뻗어 있고 당신은 그 끝을 잡고 있다. 뛰어내리면 이 목표물을 중심으로 반시계 방향으로 돌기 시작한다. 다른 목표물은 $(0, 0)$의 오른쪽과 위쪽에 있고 좌표는 $(x_i, y_i)$이며 $x_i \ge 0$, $y_i \ge 0$이다. 밧줄의 양 끝이 아닌 내부의 점이 목표물 하나 이상에 닿으면, 밧줄은 움직이는 끝에서 가장 가까운 목표물에서 꺾인다. 처음 속도는 무시한다. 당신은 닌자라서 속도가 충분히 빠르고, 목표물 하나만 중심으로 돌게 될 때까지 계속 목표물을 감으며 꺾인다.

밧줄의 길이는 지금 $R$이지만, 돌기 시작하기 전에 더 짧은 길이 $r$로 잘라도 된다. $r$는 정수가 아니어도 된다. 자른 뒤에는 $(-r, 0)$에서 출발해 반시계 방향으로 $(0, -r)$ 쪽으로 돈다.

한 번 도는 동안 밧줄에 만들 수 있는 꺾임은 최대 몇 개인가? 꺾임은 밧줄이 목표물에 닿은 뒤 그 목표물을 중심으로 0이 아닌 각도만큼 회전할 때 생긴다. 꺾이는 지점을 빼면 밧줄은 항상 완벽하게 곧게 유지된다. 이것도 당신이 닌자라서 가능하다. 같은 목표물을 여러 번 감아도 되고, $(0, 0)$에 있는 목표물도 다른 목표물과 똑같이 꺾이는 지점이 된다.

위 그림에는 목표물이 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개이고, 이것이 최적이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$과 $R$이 주어진다. 이어지는 $N$개의 줄에는 목표물의 좌표 $x_i$와 $y_i$가 주어지고, 첫 번째 목표물은 $(0, 0)$에 있다.

제한

• $1 \le T \le 100$
• 모든 목표물의 좌표는 정수다.
• 모든 목표물의 위치는 서로 다르다.
• 첫 번째로 주어지는 목표물은 $(0, 0)$에 있다.
• 최적해를 주는 $r$ 가운데, 길이가 $r - 0.999999$인 밧줄도 같은 해, 곧 같은 꺾임 순서를 주는 값이 적어도 하나 있다.
• $1 \le N \le 10$
• $1 \le R \le 1{,}000$
• $0 \le x_i \le 1{,}000$
• $0 \le y_i \le 1{,}000$

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