Moving Tables

A company occupies an entire floor of a building laid out as shown below. The rooms on this floor are numbered as in the figure.

There are 200 rooms on each side of the corridor, 400 rooms in total. To remodel several of them, the company must move many tables from one room to another. The corridor is narrow, so only one table can pass through it at a time.

Moving a single table from one room to another takes 10 minutes. While a table is moved from room $i$ to room $j$, the stretch of corridor from in front of room $i$ to in front of room $j$ is in use. During the same 10-minute slot, jobs whose corridor stretches do not overlap can be carried out at the same time.

For example, moving a table from room 30 to room 50 and moving one from room 60 to room 90 use disjoint stretches of corridor, so they can be done simultaneously. Moving from room 11 to room 12 and from room 14 to room 13 also do not overlap, so they can be done together.

On the other hand, moving from room 20 to room 40 and moving from room 31 to room 80 both use the corridor from in front of room 31 to in front of room 40, so they cannot be done at the same time. Likewise, moving from room 1 to room 4 and moving from room 3 to room 6 both need the corridor in front of room 3, so they cannot be done together.

Each room has at most one table entering or leaving it. Compute the minimum time needed to move all the tables.

The first line contains the number of test cases $T$.

For each test case, the first line contains the number of moves $N$ ($1 \le N \le 200$). Each of the following $N$ lines contains two positive integers $s$ and $t$, meaning that a table is moved from room $s$ to room $t$. Room numbers range from 1 to 400, and within a single test case each room number appears at most once.

For each test case, print on its own line the minimum time, in minutes, needed to finish moving all the tables.