Problem

"I say we must move forward, not backward; upward, not forward; and always twirling, twirling, twirling towards freedom!" — Former U.S. Presidential nominee Kodos.

After hearing this inspirational quote from America's first presidential nominee from the planet Rigel VII, you have decided that you too would like to twirl (rotate) towards freedom. For the purposes of this problem, you can think of "freedom" as being as far away from your starting location as possible.

The galaxy is a two-dimensional plane. Your space ship starts at the origin, position (0, 0). There are N stars in the galaxy. Every minute, you can choose a star and rotate your space ship 90 degrees clockwise around the star. You may also choose to stay where you are.

How far away can you move from the origin after M minutes?

The image illustrates the first 3 rotations for a possible path in sample case 1. Note that this path is not necessarily a part of any optimal solution.

Input

The first line of the input gives the number of test cases, T. T test cases follow, beginning with two lines containing integers N and M. The next N lines each contain two integers, X_i and Y_i, representing the locations of stars.

Output

For each test case, output one line containing "Case #x: D", where x is the case number (starting from 1) and D is the distance from the origin to the optimal final position. Answers with absolute or relative error no larger than 10^-6 will be accepted.

Limits

Memory limit: 1GB.

1 ≤ T ≤ 100;

-1000 ≤ X_i ≤ 1000;

-1000 ≤ Y_i ≤ 1000.

No two stars will be at the same location.

There may be a star at the origin.

Test set 1 (Visible Verdict; 10 Points)

Time limit: 30 6 seconds.

1 ≤ N ≤ 10.

1 ≤ M ≤ 10.

Test set 2 (Hidden Verdict; 39 Points)

Time limit: 60 12 seconds.

1 ≤ N ≤ 5000.

1 ≤ M ≤ 10⁸.

Sample

3
4
1
-2 4
1 -2
4 1
0 2
1
4
-5 0
2
5
-1 1
-2 2

Case #1: 6.3245553203
Case #2: 10.0000000000
Case #3: 6.3245553203