Have you played Super Mario? If yes, then hi5, your childhood was awesome. Now, you know Mario has to jump from one cliff to another cliff and by doing that he endangers his life. So he wants your help, so that gamers don’t have to see “Game Over” on their computer screen. Now, you will be given one standing point from which Mario has to jump and another landing point on which Mario should land to save himself from free fall. You have to print the minimum length Mario has to cover by jumping, so that he can be safe.

Warning: 1. Points will be given arbitrarily. 2. As Mario runs through x axis, only points on x-axis will be given. 3. Mario can jump in both directions.

Input

The first line of the input contains an integer T (1 <= T <= 10) number of test cases. Each test case contains an integer N (1 <= N <= 10000). N lines will follow containing two integers (standing point A (-10000 <= A <= 10000) and landing point B (-10000 <= B <= 10000).

Output

Print expected answer for each test case.

Example

Input:
2
5
1 2
3 6
1 6
2 2
5 5
2
1 1
2 3

Output:
Case 1: 5
Case 2: 1