Airport

A large city runs an international airport that handles 40 million passengers a year, yet it is infamous as one of the most congested airports in the world. As the figure shows, the airport has a single runway, so the runway is always crowded with aircraft waiting to take off. The runway can be reached from two directions, the west road $W$ and the east road $E$, and aircraft line up on these two roads to wait for takeoff.

At each time $t$, an arbitrary number of aircraft arrive on roads $W$ and $E$. When an aircraft arrives on a road at time $t$, it is given a rank equal to the number of aircraft already waiting ahead of it on the same road. After all arrivals at time $t$, the control tower picks one of the two roads, and the aircraft at the front of that road takes off and leaves the runway. Given the arrivals at every time, we want the tower's takeoff schedule that minimizes the maximum rank assigned to any aircraft.

For example, the table above lists the aircraft arriving on roads $W$ and $E$ at each time. At time 1, aircraft $A_1$, $A_2$, $A_3$ receive ranks 0, 1, 2, and aircraft $B_1$, $B_2$ receive ranks 0, 1. The tower then lets $B_1$ on road $E$ take off, and $B_1$ leaves. At time 2, aircraft $B_3$, $B_4$, $B_5$ receive ranks 1, 2, 3, and then $A_1$ on road $W$ takes off and leaves. At time 3, aircraft $A_4$, $A_5$ receive ranks 2, 3. So the maximum rank over all aircraft is 3, and this is the smallest possible maximum rank over every takeoff schedule.

The input is read from standard input. The first line contains the number of test cases $T$. Each test case is given as follows. The first line of a test case contains an integer $n$ ($1 \le n \le 5000$), the number of times. Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($0 \le a_i, b_i \le 20$), the number of aircraft arriving on road $W$ and on road $E$, respectively, at time $i$.

For each test case, print one line containing the minimum, over all takeoff schedules, of the maximum rank of the aircraft.