Nevermore is a terrible monster. When he kill a life, he will absorb its soul to improve his strength.And his ult called Requiem of Souls, is very fierce and cruel. Evil spirit will be summoned to attack nearby enemy units.The damage is related to the distance to nevermore.

To simplify the problem we assume that all enemy unit are on the x-axis. The damage is A - D, A is the initial damage, D is the distance to nevermore.Nevermore can choose anywhere to release his ult as he has a blink dagger. Your task is to call the minimum initial damage A Nevermore need to kill all enemy units by release Requiem of Souls once.(If a unit's HP less than or equal to zero, it will die.)

The first line is integer T(T <= 20), the number of test cases.The first line of each case contains a integer n (0 < n <= 10^5), the number of enemy units.Then n lines, each line contains two integer a, b(0 < a, b < 10^8), a is the enemy unit's location, b is the enemy unit's HP.

For each case, output the minimum initial damage in the sample output format.

wy