During his study in Amazing International University-Bangladesh Kazi Hossain accidentally made a space ship while doing a course assignment. He named the space ship Duronto Eagle. Now he wants to travel to other habitable planets in the galaxy with Duronto Eagle. As Kazi is a very brave guy he wants to start his space journey by travelling to the farthest planet in the galaxy first.

The co-ordinate of the planet Kazi is currently in (planet Earth) is always (0, 0). You are given the co-ordinates of the other N habitable planets in the galaxy in a 2D Cartesian plane. You have to find the index of the farthest planet considering the Euclidean distance from planet Earth (0, 0). Indices range from 1 to N.

Input

Input starts with an integer T (≤ 100), denoting the number of test cases. Each of the test cases starts with an integer N (1 ≤ N ≤ 50), denoting the number of planets. Each of the next N lines contains two integers x_i y_i (-10000 ≤ x_i, y_i ≤ 10000) describing the coordinates of the planets in the galaxy.

Output

For each case print the case number and the index of the farthest planet from Earth that Kazi will be travelling first. If there’s multiple possible answers output the one that comes first in the input. See sample input output for clarification.

Example

Input:
2
3
4 0
0 5
2 2
4
2 3
1 1
5 5
-4 -1

Output:
Case 1: 2
Case 2: 3