Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Escape Plan

By Riaz_BSMRSTU · Limits 1s, 512 MB

Hey, you are stuck on prison and you have to get out soon. This prison has one way road and you can only escape on this way. It has N doors numbered 1 to N from prison cell and there is a guard on each door. However, each guard will go on a vacation, and after spending his vacation he will be back. One guard will go on vacation for only one time. To escape from the prison, you have to pass all the door and if any guard on any door is not on vacation on a day, you can't pass that door on that day. To pass a door you need one day and you can't wait while you passing doors.

Now, somehow you got the list of vacation range for every guard. You have to find out a good day to start escaping. Escape as soon as possible.

Input

Input start with T (1 ≤ T ≤ 10), number of test cases.
Each case contains N (1 ≤ N ≤ 105), the number of doors.
Each of next N line contains Li and Ri (1 ≤ LiRi ≤ 106), which means guard on ith door will be on vacation from Li day to Ri day.

Output

For each case, print the day number when you will start escaping. If you can't escape print "I'm Stuck :(".

Sample

InputOutput
2
2
1 1
2 2
2
2 2
2 2
1
I'm Stuck :(

    Discussion

    Statistics


    62% Solution Ratio

    naimulhasanEarliest, 4w ago

    RamprosadGFastest, 0.0s

    naimulhasanLightest, 131 kB

    MursaleenShortest, 439B

    Submit

    Login to submit