Alice must go to school everyday, but she wants to make the journey interesting, so she would like to play a game this time.

There are n stones on the road,  Alice go though these stones step by step. In each step, Alice could go to the next nearest stone. She will throw this stone ahead if the current number of step is odd, otherwise, she will skip it.  Now, you have the information about the stones, i.e., each stone has two attributes: P_i  (the position of that stone) and D_i (the throw distance of that stone), and you are asked to find the largest distance Alice could walk. 

Please note that if there are two or more stones at the same position, Alice will go to the one with the smallest D_i first.

The first line will be an integer T, which is the number of test cases. (1 <= T <= 3). For each test case, the first line will be an integer n(1 <= n <= 10⁵), then followed by n lines, each line will be two integers P_i(1 <= P_i <= 10⁹) and D_i(1 <= D_i <= 10⁹), P_i means the position of the i-th stone, D_i means how far Alice can throw it.

Output one line for each test, the largest distance Alice could walk.

If there is a stone, its position is P_i and its throw distance is D_i,  and you can throw it, it can only be threw to the position P_i  + D_i