아이슬란드 모터클럽

아이슬란드에는 폭포, 용암 지대, 절벽, 간헐천, 계곡, 화산, 빙하가 있고 고래와 물개, 양도 산다. 최근 이 나라에 모터클럽이 몰리고 있다. 리얼리티 방송으로 실체가 드러나 고국에서 쫓겨난 회원들은 이제 다른 곳에서 오토바이를 탄다. 이들은 돈이 아주 많아서 개인 비행기를 굴리고, 오토바이와 함께 낙하산으로 원하는 지점 어디에나 내린다.

아이슬란드의 도로는 대부분 오토바이로 달리기 어렵지만, 섬을 한 바퀴 도는 포장된 순환도로가 하나 있다. 이 도로는 볼 만한 명소를 모두 지난다. 인구가 적어 주유소는 많지 않고, 혹독한 겨울에는 한 바퀴를 겨우 돌 만큼만 연료가 공급된다. 겨울에 눈이 치워진 차선은 시계 방향 안쪽 차선뿐이다. 아이슬란드는 우측통행이다.

라이더는 각 주유소에 남은 연료량과 이웃한 두 주유소 사이의 거리를 안다. 오토바이의 연료 탱크는 용량이 무제한이라고 본다. 대신 가득 찬 탱크는 기압에 찌그러지므로 라이더는 빈 탱크로 비행기에서 뛰어내린다. 출발 주유소를 포함해 주유소에 도착할 때마다 그곳에 있는 연료를 남김없이 넣는다. 오토바이는 1마일을 달리는 데 연료 1리터를 쓴다.

주유소마다 있는 연료량과 이웃한 주유소 사이의 거리가 주어질 때, 연료가 떨어지지 않고 시계 방향으로 한 바퀴를 완주할 수 있는 출발 주유소를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

• 첫 줄에 순환도로에 있는 주유소의 수 $N$이 주어진다 ($3 \le N \le 10^6$). 주유소 번호는 1번부터 $N$번까지다.
• 이어지는 $N$개의 줄에 주유소 하나의 정보가 공백으로 구분된 두 정수 $G$와 $D$로 주어진다 ($0 \le G \le 512$, $1 \le D \le 512$). $G$는 그 주유소에 있는 연료의 양(리터), $D$는 시계 방향으로 다음 주유소까지의 거리(마일)다. 순환도로이므로 $N$번 주유소의 $D$는 1번 주유소까지의 거리다.

각 테스트 케이스마다 한 줄에 한 바퀴를 완주할 수 있는 출발 주유소의 번호를 출력한다. 그런 주유소가 여럿이면 번호가 가장 작은 것을 출력한다. 어느 주유소에서 출발해도 완주가 불가능하면 그 줄에 IMPOSSIBLE을 출력한다.