Time Limit: Java: 1000 ms / Others: 1000 ms

Memory Limit: Java: 32768 KB / Others: 32768 KB

## Description

There are two machines A and B. There are n tasks, namely task 1, task 2, ..., task n. You must assign each task to one machine to process it. There are some facts you must know and comply with:

• You must assign each task to only one machine to process.
• At any time, a machine can process at most one task.
• Task i (0 < i < n) can be processed if and only if each task j (0 < j < i) has been processed or processing.
• If a task is processing on one machine, it cannot be interrupted.

You want to do finish all the tasks as soon as possible.

## Input

There are multiple test cases. The first line of the input is an integer T (0 < T < 1000) indicating the number of test cases. Then T test cases follow. Each test case starts with an integer n (0 < n < 100). The ith line of the next n lines contains two integers tA, tB (0 < tA, tB < 100), giving the time to process the ith task by machine A and machine B.

## Output

For each test case, output the earliest time when all the tasks have been processed.

## Sample Input

4
1
1 2
2
1 2
2 1
2
1 2
90 95
3
1 3
1 3
1 3

## Sample Output

1
1
90
3

## Hint

• Test case 1: Let machine A process task 1.
• Test case 2: Let machine A process task 1 and at the same time let machine B process task 2.
• Test case 3: Let machine B process task 1 and at the same time let machine A process task 2.
• Test case 4: Let machine A process all the tasks.

## Source

The 7th Zhejiang Provincial Collegiate Progra