There are n pizza to be made. For each pizza, there is a golden baking time range [ai, bi). If a cook is assigned to this pizza, during time range [ai, bi) the cook cannot do anything else but take care of this pizza with all his heart. The cook crew found out that the number of cooks in the crew was just fit for all pizza. That is, with absence of any cook, the whole crew cannot make all pizza done within golden baking time.
Recently, they realized that they must extend the golden baking time due to global warming. All golden baking time must extended by c, that is, [ai, bi+c) for the i-th pizza. Find the maximum integer c such that all pizzas can be cooked in its golden baking time.
The first line of the input file contains an integer T (1<= T<= 100) indicating the number of test cases.
For each test case, first line contains an integer n (1<= n<= 100000). Each of the next n lines contains two integers ai, bi. (0<= ai<= bi<= 1018)
For each test case, output the maximum integer c that satisfies the above condition. If there is no such maximum integer, please output -1.
3 3 1 2 3 4 5 6 3 1 2 2 3 2 4 3 1 2 1 3 1 4
1 0 -1
Migrated from old NTUJ.
Tmt, Ferng
| No. | Testdata Range | Score |
|---|