URI Online Judge | 1554

N.1 Continuous

By M.C. Pinto, UFFS BR Brazil

Timelimit: 1

There are a lot of cue sports. The UFFS (Union of Fascinated Fans of Sports) has developed a new variant of Straight pool, called N.1.

In this variant the shooter may try to hit the white ball at its closest ball at the pool table, among N possible ones. The match is won by the player that gets more hits after 50 attempts.

The game difficulty is at finding out which of the N balls is the closest one to the white. Your task is to write a program that helps the match judges.

Input

There are several test cases. The first line of input contains an integer C that determines the number of test cases. For each test case, the input begins with an integer N (1 ≤ N ≤ 50), which defines the number of available balls, besides the white one. The next N + 1 lines contain two integers, x and y, separated by a blank space, indicating the (x, y) ball position on the pool table, one ball for each line (0 < x < 1420 mm e 0 < y < 2840 mm). The first line indicates the position of the white ball. The rstrongaining ones indicate the position of the balls 1, 2, 3,. . . , N-1, N in that order.

Output

For each test case print a line containing only the number of the ball that is closest to the white one. The error allowed is 0.01 mm. If more than one ball satisfy the minimum distance, you must show the smallest number among the tied ones. Always end a line with the new line character (\n).

Sample Input Sample Output

3
1
30 60
900 1800
2
710 30
710 2100
710 1000
3
710 30
710 2100
510 1000
910 1000

1
2
2