1285_E. Delete a Segment
There 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 ≤ x ≤ 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 ≤ t ≤ 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 ≤ n ≤ 2⋅10^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 ≤ l_i ≤ r_i ≤ 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⋅10^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
```python
import io
import os

from collections import Counter, defaultdict, deque

# From: https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


class SegmentData:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c


def pack(a, b, c):
    return SegmentData(a, b, c)
    return [a, b, c]
    return (a, b, c)
    return (a << 40) + (b << 20) + c


def unpack(abc):
    return abc.a, abc.b, abc.c
    return abc
    return abc
    ab, c = divmod(abc, 1 << 20)
    a, b = divmod(ab, 1 << 20)
    return a, b, c


def merge(x, y):
    # Track numClose, numNonOverlapping, numOpen:
    # e.g., )))) (...)(...)(...) ((((((
    xClose, xFull, xOpen = unpack(x)
    yClose, yFull, yOpen = unpack(y)
    if xOpen == yClose == 0:
        ret = xClose, xFull + yFull, yOpen
    elif xOpen == yClose:
        ret = xClose, xFull + 1 + yFull, yOpen
    elif xOpen > yClose:
        ret = xClose, xFull, xOpen - yClose + yOpen
    elif xOpen < yClose:
        ret = xClose + yClose - xOpen, yFull, yOpen
    # print(x, y, ret)
    return pack(*ret)


def solve(N, intervals):
    endpoints = []
    for i, (l, r) in enumerate(intervals):
        endpoints.append((l, 0, i))
        endpoints.append((r, 1, i))
    endpoints.sort(key=lambda t: t[1])
    endpoints.sort(key=lambda t: t[0])

    # Build the segment tree and track the endpoints of each interval in the segment tree
    data = []
    # Note: defaultdict seems to be faster. Maybe because it traverses in segment tree order rather than randomly?
    idToIndices = defaultdict(list)
    for x, kind, intervalId in endpoints:
        if kind == 0:
            data.append(pack(0, 0, 1))  # '('
        else:
            assert kind == 1
            data.append(pack(1, 0, 0))  # ')'
        idToIndices[intervalId].append(len(data) - 1)
    assert len(data) == 2 * N
    segTree = SegmentTree(data, pack(0, 0, 0), merge)
    # print("init", unpack(segTree.query(0, 2 * N)))

    best = 0
    for intervalId, indices in idToIndices.items():
        # Remove the two endpoints
        i, j = indices
        removed1, removed2 = segTree[i], segTree[j]
        segTree[i], segTree[j] = pack(0, 0, 0), pack(0, 0, 0)

        # Query
        res = unpack(segTree.query(0, 2 * N))
        assert res[0] == 0
        assert res[2] == 0
        best = max(best, res[1])
        # print("after removing", intervals[intervalId], res)

        # Add back the two endpoints
        segTree[i], segTree[j] = removed1, removed2

    return best


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    T = int(input())
    for t in range(T):
        (N,) = [int(x) for x in input().split()]
        intervals = [[int(x) for x in input().split()] for i in range(N)]
        ans = solve(N, intervals)
        print(ans)

```