Escape Plan

Riaz_BSMRSTU BSMRSTU Monthly Contest,...
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 :(

Submit

Login to submit.

Statistics

71% Solution Ratio
naimulhasanEarliest, Dec '20
RamprosadGFastest, 0.0s
naimulhasanLightest, 131 kB
Rakib105Shortest, 305B
Toph uses cookies. By continuing you agree to our Cookie Policy.