Ninjutsu is the martial art of the mysterious Japanese assassins, ninja. As a beginner in the practice of ninjutsu, your first task is to master the use of the grappling hook.
A grappling hook is a technologically-advanced device consisting of a hook tied to some (very strong and very thin) rope. Proper use of a grappling hook involves throwing the hook at a target and hoping that it catches.
This time, it did! You are now hooked onto a target that is located at (0,
0). Your rope extends to the left, and you're at the end of it; when you jump,
you will start swinging counter-clockwise around the target. There are other
targets located to the right and above (0, 0), at (xi,
Your rope currently has length R, but you may choose to cut it down to
any shorter length r (including non-integers) before you start swinging.
As such, you will start at
What is the maximum number of bends you can put into the rope with one swing? A bend happens when your rope touches a target and then rotates some non-zero number of degrees around that target. The rope will always remain perfectly straight (again, this is possible because you are a ninja), except at bends.
In the example above, there are 6 points:
If, however, you cut the rope by 0.18 units, you will not have enough
length to reach point
(0, 0)--(12, 4)--(14, 5)--(13, 7)--(12, 4)--(14, 5)and will end up orbiting point
Case #1 in the sample input below represents this example.
The input will start with a line containing T, the number of test cases to follow. Each test case will start with two integers together on a line: N and R. The next N lines will each contain a pair of integers -- xi and yi -- the coordinates of the targets, starting with the target at (0, 0).
OutputFor each test case, output a line of the form "Case #C: k", where C is the 1-based case number, and k is the maximum number of bends that can be made in the rope in one swing.
Limits1 ≤ T ≤ 100
Small dataset1 ≤ N ≤ 10
Large dataset1 ≤ N ≤ 1,000