C :: From My Moon to the Titan's Moons

Time Limit: 10 Seconds    Memory Limit: 32768 KB

 There's a competition, sponsored by a company named XpaceS in planet Titan which has N moons. To enter the competition any participant has to complete the first task which is to put their team flag on all the moons in a specific order and land on the first moon they have started the task on, using the fuel available on the moons.

  The order is circular so for N=3, they can put the flag in the order M0, M1, M2, M0 or M1, M2, M0, M1 or M2, M0, M1, M2. It's up to the participants to choose their starting moon.

  The only restriction is that the spaceship they want to use to carry the flags should not have any fuel in the beginning and they should only use the fuel that is available on each moon.

  Each moon i has a supply of Fi units of fuel that the spaceship can use to refuel once landed on the moon Mi. The spaceship's fuel tank is so large that it practically has infinite capacity.

  If you want to finish this task, you need to be clever about choosing your starting moon. So write a program to find it.

 

Input

  The first line contains the number of test cases T (1 ≤ T ≤ 256).

  Each test case begins with one integer N (2 ≤ N ≤ 10000) the number of moons, then N lines will follow, each contains two non-negative integers Fi, the amount of fuel, and Di, the distance to the next moon. Dn-1 is the distance from the last moon to the first one.

  The spaceship consumes one unit of fuel per one unit of distance.

Output

  For each test, print one integer in one line, the ID number of the moon that could be the starting point. The ID of the first moon is 0, next is 1, and so on. If there are more than one possible starting moons, output the one that comes first in the input. If there is no such starting moon to finish the task, just output "it's a trap".

Sample Input

3
3
100 100
100 100
100 100
2
100 200
200 100
2
100 200
100 200

Sample Output

0
1
it's a trap
Submit

Source: 15th Iran Nationwide Internet Contest