Ninjutsu (Small)

Ninjutsu is the martial art of the Japanese assassins called ninja. You are a beginner, and your first task is to master the grappling hook.

A grappling hook is a hook tied to a very strong and very thin rope. You use it by throwing the hook at a target and hoping that it catches.

This time it caught. You are hooked onto a target at $(0, 0)$. The rope extends to the left and you hold its far end. When you jump, you start swinging counterclockwise around that target. The other targets sit to the right of and above $(0, 0)$, at $(x_i, y_i)$ with $x_i \ge 0$ and $y_i \ge 0$. When an interior point of the rope, that is a point which is not either end, touches one or more targets, the rope bends around the target closest to its moving end. Ignore your starting velocity. You are a ninja, so it is fast enough that you keep bending around targets until you are spinning around a single one.

The rope has length $R$ right now, but before you start swinging you may cut it down to any shorter length $r$. The value of $r$ does not have to be an integer. You then start at $(-r, 0)$ and swing counterclockwise toward $(0, -r)$.

What is the largest number of bends you can put into the rope in one swing? A bend happens when the rope touches a target and then rotates a nonzero number of degrees around that target. Away from the bends the rope always stays perfectly straight, which is again possible because you are a ninja. You may wrap around the same target several times, and the target at $(0, 0)$ is a bending point just like every other target.

The picture above has 6 targets.

• $(0, 0)$
• $(3, 1)$
• $(12, 4)$
• $(14, 5)$
• $(13, 7)$
• $(7, 10)$

The rope has length $24$. If you do not cut it, you bend around $(12, 4)$, then around $(14, 5)$, then around $(13, 7)$, and you end up orbiting $(7, 10)$ with about $0.1705$ units of rope left. That is 4 bends in total. You do touch $(3, 1)$, but it produces no bend because it is collinear with $(0, 0)$ and $(12, 4)$.

If instead you cut $0.18$ units off the rope, you can no longer reach $(7, 10)$, so you follow the path

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

and end up orbiting $(14, 5)$ with about $1.3004$ units of rope left. That path has 5 bends in total, and it is optimal.

The first line has $T$, the number of test cases. The first line of each test case has two integers $N$ and $R$. The next $N$ lines each have the coordinates $x_i$ and $y_i$ of a target, starting with the target at $(0, 0)$.

Limits

• $1 \le T \le 100$
• All target coordinates are integers.
• All targets are at different positions.
• The first target listed is at $(0, 0)$.
• At least one value of $r$ that gives an optimal answer has the property that a rope of length $r - 0.999999$ gives the same solution, meaning the same sequence of bends.
• $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$

For each test case, print one line of the form "Case #$C$: $k$", where $C$ is the 1-based test case number and $k$ is the largest number of bends that can be made in the rope in one swing.