Icelandic Motorclubs

Iceland has waterfalls, lava fields, cliffs, geysers, valleys, volcanoes and glaciers, plus whales, seals and sheep. Motor clubs have recently taken an interest in the country. Thrown out of their home countries after reality TV showed what they get up to, the members now ride elsewhere. They have a lot of money, so they own private planes and parachute in with their motorcycles wherever they like.

Most roads in Iceland are too rough for a motorcycle, but one paved ring road circles the island and passes every sight worth stopping for. The country is thinly populated, so there are few gas stations, and in a hard winter they hold barely enough gas for a single lap. In winter only the inner clockwise lane is clear of snow, since Iceland drives on the right.

A rider knows how much gas sits at every station and how far apart neighbouring stations are. The gas tank on the motorcycle is treated as having infinite capacity. A full tank collapses under air pressure, so the rider jumps out of the plane with an empty tank. At every station, including the starting one, the rider takes all the gas that is there. The motorcycle burns one liter of gas per mile.

Given the amount of gas at each station and the distance between neighbouring stations, find a station the rider can start from and complete one clockwise lap without running out of gas.

The first line contains an integer $T$, the number of test cases. Each test case looks like this.

• One line with an integer $N$, the number of gas stations on the circular road ($3 \le N \le 10^6$). The stations are numbered 1 through $N$.
• $N$ lines, each describing one gas station with two space separated integers $G$ and $D$ ($0 \le G \le 512$, $1 \le D \le 512$). $G$ is the amount of gas at that station in liters and $D$ is the distance in miles to the next station clockwise. The road is circular, so the $D$ of station $N$ is the distance to station 1.

For each test case, print one line with the number of a gas station the rider can start the lap from. If several stations work, print the smallest number. If no station allows a full lap, print IMPOSSIBLE on that line instead.