You have a radio receiver and want to receive N messages. Each message is transmitted at a predetermined time measured in seconds since the epoch. Also each message is transmitted from a predetermined position representing the displacement in meters from the origin (you are in 1-dimensional space). Your radio is capable of receiving any message that is transmitted no farther than D meters from your current position, where Dis a nonnegative real number.

You can start at any position of your choice and move at the rate of at most one meter per second. The action of receiving a message itself takes no time. Your task is to find the smallest D that allows you to get all messages.

Input

The first line of input gives the number of test cases, C. C test cases follow. For each test case there will be:

• One line containing the integer N, the number of messages.
• N lines corresponding to the N messages where each of them contains 2 integers P and T separated by one space. P is the position where the message is transmitted from and T is the time when this message is transmitted (The messages will have distinct transmission times).

Output

For each test case, output one line containing "Case #x: ", where x is the number of the test case, followed by the minimum value D that allows you to get all messages. Answers with a relative or absolute error of at most 10^-9 will be considered correct.

Limits

• 1 ≤ C ≤ 100
• 1 ≤ N ≤ 1000

Small Dataset (15 points)

• 0 ≤ P ≤ 1000
• 0 ≤ T ≤ 1000

Small Dataset (25 points)

• 0 ≤ P ≤ 10⁹
• 0 ≤ T ≤ 10⁹

Example

Input

3
3
7 2
20 3
0 11
2
6 5
6 3
4
5 3
2 1
9 4
7 2

Output

Case #1: 6
Case #2: 0
Case #3: 2.00

Here is one possible scenario with D = 6 for test case #1. Start at position 13 and time 2 to get message 0. Then walk to the right to position 14, arriving at time 3 to get message 1. Then walk left to position 6, arriving at time 11 to get message 2.