Airplane Parking

Jack has started a new business: a parking lot for airplanes. He bought a large but very narrow strip of land, so airplanes can only enter and leave in Last-In First-Out (LIFO) order; the lot behaves exactly like a stack (see the picture below). There is no way to pull an airplane out from the back to let others move, so the airplane parked most recently must always be the first to leave.

Because of this restriction it is not always possible to satisfy every parking request. Each request consists of a planned arrival time and a planned departure time. The table below shows the requests of 4 airplanes.

Here airplanes 1, 2, and 4 can be accepted together, but airplanes 2 and 3 cannot both be accepted.

Different airplanes may share the same planned arrival time or the same planned departure time. Jack's crew is highly skilled: whenever a valid parking order exists, they will find it. Consider another example.

Although airplanes 5 and 6 arrive at the same time, the crew knows airplane 5 must leave before airplane 6, so they park airplane 6 first and airplane 5 on top of it.

Given a list of parking requests, determine the maximum number of airplanes that can be parked, given that airplanes may only leave in Last-In First-Out order.

The first line contains an integer $T$, the number of test cases ($1 \le T \le 5$). Each test case has the following format.

The first line contains an integer $N$ ($1 \le N \le 300$), the number of airplanes. Each of the next $N$ lines contains two integers $S_i$ and $T_i$ ($0 \le S_i < T_i \le 10^9$): the planned arrival time and planned departure time of airplane $i$.

For each test case, print a single line containing one integer: the maximum number of airplanes that can be parked in Jack's parking lot.