18721번 - Clique 다국어

문제

Consider a circle divided into 10⁶ arcs numbered clockwise from 1 to 10⁶. Moreover, 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 share at least one common arc.

입력

The first line of input contains the number of test cases z. The descriptions of the test cases follow.

The first line of each test case contains the number of segments n (1 ≤ n ≤ 3000). The following n lines contain two integers l_i and r_i (1 ≤ l_i, r_i ≤ 10⁶) – the first and last arc of the i-th segment if we traverse the circle clockwise. No segment contains the entire circle, and no two segments coincide.

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

출력

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

제한

힌트