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

hide comments
Ranjan Kumar Singh: 2014-07-30 17:46:08

be carefull for eqality cases in internal and external diameter

Sahil Dua: 2014-07-16 19:06:32

Such an easy problem, but still WA!
Are there any tricky cases?
EDIT: got AC finally

Last edit: 2014-10-24 12:30:19
Rajat (1307086): 2014-06-24 01:04:25

can outer radii be less than inner radius for same ring? (though logically incorrect) I think in this problem it can be.Coz I found the ring with largest inner radii and then compared with all other.But it gave wrong answer. This shows this.

Last edit: 2014-06-24 01:08:07
who cares: 2014-05-01 19:01:22

hmmm

Jitesh: 2014-04-11 20:28:19

Why SIGABRT ??

vikrant: 2014-02-17 15:30:47

Ac in first attempt :)

ping_of_death: 2014-02-13 22:20:25

Accepted in first go!!!!!!!.....a small exercise for brain

Vipul Pandey: 2013-12-31 22:38:59

easy but not that much to be in tutorial.
Got AC in first go.

JordanBelfort: 2013-12-29 20:27:21

tutorial stuff

[Lakshman]: 2013-12-28 17:29:34

@Roman I m not aware of pascal but I think ur algo is wrong.Post ur code in forum if u need help.


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