Clique

Time limit25sMemory limit512 MB

Summary

Given n arcs on a circle of 10^6 arcs, find the largest number of arcs where every pair shares at least one arc.

Level: Medium7 of 10
Topics: Intervals, Sorting, Geometry
Solved: No attempts yet

Problem

A circle is divided into $10^6$ arcs numbered clockwise from 1 to $10^6$ . There are $n$ segments on the circle, each spanning a connected interval of arcs.

Find the size of the largest set of segments such that every two of them share at least one common arc.

Input

The first line contains the number of test cases $z$ . Each test case begins with a line containing the number of segments $n$ ( $1 \le n \le 3000$ ). The following $n$ lines each contain two integers $l_i$ and $r_i$ ( $1 \le l_i, r_i \le 10^6$ ), the first and last arc of the $i$ -th segment when traversed clockwise. No segment covers the entire circle, and no two segments are the same.

The sum of $n$ over all test cases does not exceed 24000.

Output

For each test case, output a single line containing one integer: the size of the largest set of segments such that every two of them intersect.

Examples1

Example 1
Input
```
1
4
1 4
4 5
5 2
3 3
```
Expected output
```
3
```