DRNTEAGL - Duronto Eagle


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 xi yi (-10000 ≤ xi, yi ≤ 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

hide comments
tikawim: 2023-07-30 20:13:34

-1 For wrong formatted input planets coords.

phoemur: 2023-07-30 01:54:48

easy peasy

Simes: 2023-02-10 13:17:38

Thumbs down -1 for badly formatted input

dragoncat: 2022-03-13 15:50:31

Pythagoras

nadstratosfer: 2019-10-13 08:31:25

Input features blanklines and some coordinates are not on the same line. Read integers one by one C-style to avoid NZEC in Python.

n_a_b_h_a_n: 2019-04-19 07:20:29

after every test case of input i am printing my output,but as the example the output shows after taking all the input. Do i have to do the same was?

stoneark: 2017-12-19 10:19:03

Test cases don't comply with the input format description, cause runtime error.

elknhns: 2017-10-08 02:53:37

Finally I got AC!!
Hint: The output is case-sensitive

rohanporeddy: 2017-09-17 16:41:22

My input is correct in ideone. But it is showing wrong answer. Please help me anyone?

priyance: 2016-11-01 18:21:35

I got right answer on ideone but it is giving wrong answer on spoj. Why is it so?


Added by:imranziad
Date:2015-10-07
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB Beginners Team Formation Contest (Round 5) Onsite