BWIDOW - Black Widow Rings

Black Widow has a collection of N (numbered 1 to N) Rings. She uses the rings to attack the enemies. She has decided to use one ring for distraction. She will first throw the distraction ring and then all the other rings will be thrown through it (one at a time). Each ring has an inner and outer radius.

A ring R1 will pass through ring R2 only if the outer radius of R1 is less than the inner radius of R2.

If she can chose a distraction ring from the given collection print the index of the ring (1-based), else print -1.

Input

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of Rings.
Next N lines consists of Inner and Outer Radius of the ith Ring - r, R.

  • 1T100
  • 2N1000
  • 1r < R107

(Edited: r and R are integer)

Output

For each test case print the desired result in separate line.

Example

Input:
2
3
2 3
6 8
3 5
3
4 5
5 8
3 10

Output:
2
-1

Added by:BLANKRK
Date:2013-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Code Weavers 2013

hide comments
2015-07-17 11:38:19 SangKuan
easy.got wa due to forget invoke the start function
2015-07-03 03:31:45
why no. of submissions is less for such an easy problem
2015-06-30 09:58:43 kp
easy........dont think much
2015-05-19 16:45:52 :.Mohib.:
Easy.... O(N)
Ignore the comment of RUDRA... it can confuse.... just implement as asked and AC :)
2014-12-23 11:21:24 .::Austin::.
Easy :)
2014-12-09 16:54:56 :(){ :|: & };:
O(N) is possible.
2014-12-06 18:13:28 Naivedya Bansal
each ring passes one by one through the same distraction ring right??

Last edit: 2014-12-06 18:15:32
2014-11-05 15:38:08 RUDRA
@Rajat (1307086) ,No.
@all,Question is not clear.
...and then all the other rings will
It should be ...all the other remaining rings...
AND If you think that I am wrong:consider this test case:
1
3
2 10
6 8
3 5
output is 2.(It is possible only if my argument is true!!)

Last edit: 2014-11-05 15:41:20
2014-10-18 20:00:08 Ayush Garg
AC in 1st attempt... feeling good that accuracy is increasing in easy questions :)
2014-09-22 18:24:14 Rahul Jain
Easy one...AC in first go. :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.