시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 6 2 2 40.000%

문제

For all real numbers a ≤ b, the closed interval [a, b] refers to the set of all real numbers between a and b, inclusive. For example, [3, 5] = {x ∈ \(\mathbb{R}\) | 3 ≤ x ≤ 5}.

Bob has n closed intervals, denoted [a1, b1], [a2, b2], . . ., [an, bn], such that for all distinct i, j ∈ {1, 2, . . . , n},

  • ai and bi are positive integers.
  • ai ≤ bi. I.e., [ai, bi] is not empty.
  • ai ≠ bj, ai ≠ aj and bi ≠ bj. I.e., distinct closed intervals do not have any common endpoint.

He wants to color each of the n closed intervals monochromatically such that any two distinct overlapping intervals are in different colors. Bob wonders how many colors are needed. In other words, he wants to find the minimum positive integer k such that each of the n closed intervals can be labelled with one of 1, 2, . . ., k in a way that any two distinct overlapping intervals are labelled differently. Please help him.

입력

The first line contains the number T of test cases. Each of the next T lines specifies a test case by providing n, a1, b1, a2, b2, . . ., an, bn, in that order. Two consecutive numbers in a line are separated by one or more spaces.

You may assume:

  • 1 ≤ T ≤ 10
  • n ∈ {2, 3, . . . , 100000}
  • ai and bi are positive integers less than or equal to 232 − 1 for each i ∈ {1, 2, . . . , n}.

출력

For each test case, output the minimum positive integer k such that each of [a1, b1], [a2, b2], . . ., [an, bn] can be labelled with one of 1, 2, . . ., k in a way that any two distinct overlapping intervals are labelled differently.

예제 입력 1

3
4 1 2 3 5 4 8 6 7
5 2 5 1 10 3 7 4 6 8 9
4 3 7 4 5 2 9 6 8

예제 출력 1

2
4
3

힌트