Problem

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 (x_i, y_i)) with x_i ≥ 0 and

y_i ≥ 0 When an interior point of the rope (not either end) contacts one or more targets, the rope will bend around the target closest to its moving end. Ignore your starting velocity; because you are a ninja, it is fast enough that you will continue bending around targets until you are spinning around a single one.

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 (-r, 0) and swing down (counter-clockwise) toward (0, -r).

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.

Example

In the example above, there are 6 points:

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

You have a rope of length 24. If you do not cut the rope, then you will bend around point (12, 4), then around point (14, 5), then around point (13, 7), and finally, you will be stuck orbiting point (7, 10) with about 0.1705 units of rope remaining. This amounts to a total of 4 bends. Although you touch point (3, 1), it does not contribute a bend because it is collinear with the points

(0, 0) and (12, 4).

If, however, you cut the rope by 0.18 units, you will not have enough length to reach point (7, 10) and will instead follow the path

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

and will end up orbiting point (14, 5) with about 1.3004 units of rope remaining. This path amounts to 5 bends, in total, and is an optimal solution.

Case #1 in the sample input below represents this example.

Input

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 -- x_i and y_i -- the coordinates of the targets, starting with the target at (0, 0).

Output

For 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.

Limits

Time limit: 60 10 seconds per test set.

Memory limit: 1GB.

1 ≤ T ≤ 100

All target coordinates are integers.

All targets will be at different locations.

The first target listed will be located at (0, 0).

There will be at least one value of r that gives an optimal solution and has the property that a rope of length r - 0.999999 also gives the same solution (the same sequence of bends).

Small dataset (Test set 1 - Visible; 11 Points)

1 ≤ N ≤ 10

1 ≤ R ≤ 1,000

0 ≤ x_i ≤ 1,000

0 ≤ y_i ≤ 1,000

Large dataset (Test set 2 - Hidden; 23 Points)

1 ≤ N ≤ 1,000

1 ≤ R ≤ 10⁹

0 ≤ x_i ≤ 10⁹

0 ≤ y_i ≤ 10⁹

Sample

6
6 24
0 0
3 1
12 4
14 5
13 7
7 10
2 1
0 0
2 0
2 1
0 0
1 0
2 10
0 0
4 0
3 50
0 0
9 0
10 0
3 12
0 0
3 0
3 4

Case #1: 5
Case #2: 0
Case #3: 0
Case #4: 2
Case #5: 12
Case #6: 3