Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Delete a Segment

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere are $$$n$$$ segments on a $$$Ox$$$ axis $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$, ..., $$$[l_n, r_n]$$$. Segment $$$[l, r]$$$ covers all points from $$$l$$$ to $$$r$$$ inclusive, so all $$$x$$$ such that $$$l \le x \le r$$$.

Segments can be placed arbitrarily — be inside each other, coincide and so on. Segments can degenerate into points, that is $$$l_i=r_i$$$ is possible.

Union of the set of segments is such a set of segments which covers exactly the same set of points as the original set. For example:

- if $$$n=3$$$ and there are segments $$$[3, 6]$$$, $$$[100, 100]$$$, $$$[5, 8]$$$ then their union is $$$2$$$ segments: $$$[3, 8]$$$ and $$$[100, 100]$$$;
- if $$$n=5$$$ and there are segments $$$[1, 2]$$$, $$$[2, 3]$$$, $$$[4, 5]$$$, $$$[4, 6]$$$, $$$[6, 6]$$$ then their union is $$$2$$$ segments: $$$[1, 3]$$$ and $$$[4, 6]$$$.

Obviously, a union is a set of pairwise non-intersecting segments.

You are asked to erase exactly one segment of the given $$$n$$$ so that the number of segments in the union of the rest $$$n-1$$$ segments is maximum possible.

For example, if $$$n=4$$$ and there are segments $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$, then:

- erasing the first segment will lead to $$$[2, 3]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$ remaining, which have $$$1$$$ segment in their union;
- erasing the second segment will lead to $$$[1, 4]$$$, $$$[3, 6]$$$, $$$[5, 7]$$$ remaining, which have $$$1$$$ segment in their union;
- erasing the third segment will lead to $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[5, 7]$$$ remaining, which have $$$2$$$ segments in their union;
- erasing the fourth segment will lead to $$$[1, 4]$$$, $$$[2, 3]$$$, $$$[3, 6]$$$ remaining, which have $$$1$$$ segment in their union.

Thus, you are required to erase the third segment to get answer $$$2$$$.

Write a program that will find the maximum number of segments in the union of $$$n-1$$$ segments if you erase any of the given $$$n$$$ segments.

Note that if there are multiple equal segments in the given set, then you can erase only one of them anyway. So the set after erasing will have exactly $$$n-1$$$ segments.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test. Then the descriptions of $$$t$$$ test cases follow.

The first of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) — the number of segments in the given set. Then $$$n$$$ lines follow, each contains a description of a segment — a pair of integers $$$l_i$$$, $$$r_i$$$ ($$$-10^9 \le l_i \le r_i \le 10^9$$$), where $$$l_i$$$ and $$$r_i$$$ are the coordinates of the left and right borders of the $$$i$$$-th segment, respectively.

The segments are given in an arbitrary order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output

Print $$$t$$$ integers — the answers to the $$$t$$$ given test cases in the order of input. The answer is the maximum number of segments in the union of $$$n-1$$$ segments if you erase any of the given $$$n$$$ segments.

Example

Input

3 4 1 4 2 3 3 6 5 7 3 5 5 5 5 5 5 6 3 3 1 1 5 5 1 5 2 2 4 4

Output

2 1 5

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/08/2020 18:38:12 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|