The party began, the greasy uncle was playing cards, the fat otaku was eating, and the little beauty was drawing.

After playing cards for a while, ZJH felt very hungry. He decided to let the automatic kitchen grill steak for him. It can make the kitchen quite busy, because ZJH tastes food very strictly, especially steak!

To grilling a steak, ZJH believes that it required N grilling processes in order, each function within a temperature range for one minute, only in this case the grilled steak is the best.

Fortunately, the device in the kitchen has already been equipped with artificial intelligence, which can quickly complete the whole process in the shortest time. The temperature of this device can be increased or decreased by one degree per minute. When the temperature is within the required temperature range, the steak will be grilled for one minute. However, the trouble now is that ZJH forgot to write a program to calculate the completion time of the steak when remodelling the automatic kitchen system, so you are asked to add this program to the system.

Given an integer N, indicating the number of processes, and N pairs of numbers , representing the temperature range required by each function. The initial temperature of the device is 0. Your program should tell ZJH how long it takes for each steak to be grilled.

There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 10), indicating the number of test cases(number of steaks ZJH wants to eat!). For each test case:

The first line contains an integer N (1 ≤ N ≤ ), indicating the number of processes.

Then followed N lines, each line contains two integers  (0 ≤  ≤  ≤ ), indicating the temperature range of the i-th process.

For each test case, each line contains an integer, indicating the shortest time the kitchen take to grill steak each case.

2
3
1 5
4 6
2 3
3
0 6
0 8
0 4

8
3