There is only one school in Titan. Students from different places come to learn here. Different peoples from different places have different tastes, choices. Recently, the authority of the school has decided to make pairs of every student to make them happier. As, many students might want to make pair with a particular one, the authority imposes a rule to make pairs. They collected the heights of students and scores of their last final exams. They’ve agreed in a meeting that one student can only make pair with a student whose height is closest to the student because it will look beautiful.
Forming pair following these rules sometimes make some students unhappy. Because sometimes students with better marks may have to form pair with a student who has relatively lower marks. This makes one student unhappy. As, the authority doesn’t want to hurt any of the students, they want to find the unhappiest pair and their marks difference. Every student will choose their partner optimally following the rule.
Mad man of Titan THANOS wants you to calculate the marks differences of the unhappiest pair, as he is busy fighting with the avengers. Help him otherwise he will snap his finger.
Input
First line in the input will be T (Number of test case). (1<=T<=100)
Each test case starts with n (Number of students).
Next, n line contains 2 integers Hi and Si (Height and scores in the last exam). (2<=n<=10000, 1<= Hi, Si <=1000000000).
Height of students are distinct.
Output
For each test case There will be one line “Case #X: Y”(X for case number and Y for unhappiest pair).
Sample
| Input | Output |
|---|---|
2 3 12 100 15 200 16 400 5 1 33 2 23 3 35 4 33 5 100 | Case #1: 200 Case #2: 67 |
