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 \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

Difficulty: interview

Starter code:

Solutions:
import sys

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    intervals = [None]*n
    for i in range(n):
        intervals[i] = tuple([int(a) for a in sys.stdin.readline().split()])
    intervals = list(zip(intervals, list(range(n))))
    starts = sorted(intervals, key = lambda x: x[0][0])
    ends   = sorted(intervals, key = lambda x: x[0][1])

    connects = [0]*n
    gaps = 0
    covering = set()
    atS = 0
    atE = 0
    # print(starts)
    while atE<n:
        # print("%d, %d"%(atS, atE))
        # print(covering)
        # print(connects)
        if atS!=n and ends[atE][0][1]>=starts[atS][0][0]:
            if len(covering)==1:
               gap = list(covering)[0]
               connects[gap]+=0.5
            covering.add(starts[atS][1])
            atS += 1
            if len(covering)==1:
               gap = list(covering)[0]
               connects[gap]-=0.5

        else:
            if len(covering)==1:
               gap = list(covering)[0]
               connects[gap]-=0.5
            covering.remove(ends[atE][1])
            atE += 1
            if len(covering)==1:
               gap = list(covering)[0]
               connects[gap]+=0.5
            if len(covering)==0:
                gaps += 1
    connects = [int(a) for a in connects]
    print(max(connects)+gaps)

    

        


import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

for _ in range(t):
    n = int(input())
    segs = []
    for i in range(n):
        l,r = list(map(int, input().split()))
        segs.append((l,0,i))
        segs.append((r,1,i))
    segs.sort()
    active = set()
    increase = [0 for _ in range(n)]
    seq = []
    ans = 0
    for pos, p, i in segs:
        if p == 0:
            if len(seq)>1 and seq[-2:] == [2,1]:
                increase[next(iter(active))]+=1
            active.add(i)
        else:
            active.remove(i)
            if len(active) == 0:
                ans+=1
        seq.append(len(active))
    m = max(increase)
    seq = set(seq)
    if seq == {0,1}:
        print(ans-1)
    else:
        print(ans+max(increase))

    


        


import sys
from math import gcd

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def solve():
	n = mint()
	a = [None]*(2*n)
	c = [0]*(2*n)
	for i in range(0,2*n,2):
		l, r = mints()
		a[i] = (l*2, 0, i)
		a[i+1] = (r*2+1, 1, i)
		c[i+1] = (l*2, r*2+1)
	a.sort()
	#print(a)
	s = set()
	p = None
	start = None
	px = int(-2e9-5) # prev event
	pt = -1
	pp = px
	segs = []
	for i in range(0, 2*n):
		x, t, id = a[i]
		if px != x:
			#print(px,x)
			cd = len(s)
			if cd == 1:
				segs.append((px, x, cd, next(iter(s))))
			else:
				segs.append((px, x, cd, None))
			px = x
		if t == 0:
			s.add(id)
		else:
			s.remove(id)
	segs.append((px,int(2e9+5), 0, None))
	res = 0
	p = False
	for i in range(1,len(segs)-1):
		px, x, cd, e = segs[i]
		if e != None:
			l,r = c[e+1]
			cl = segs[i-1][2]
			cr = segs[i+1][2]
			if cl - (segs[i-1][0] >= l) > 0 \
			and cr - (segs[i-1][0] <= r) > 0:
				c[e] += 1
			if cl == 0 and cr == 0:
				c[e] -= 1
		if cd > 0 and p == False:
			res += 1
		p = (cd > 0)
	z = c[0]
	for i in range(0, 2*n, 2):
		z = max(z, c[i])
	print(res+z)

for i in range(mint()):
	solve()


debug = 0
t = int(input())

for _ in range(t):
    n = int(input())
    ev = []
    for i in range(n):
        a, b = list(map(int, input().split()))
        ev.append((a, -1, i))
        ev.append((b, 1, i))

    ev.sort()
    a = set()
    count = [0] * n
    brks = 0
    are_non_solo = 0
    if debug: print (ev)
    for j in range(2 * n):
        t, d, i = ev[j]
        if debug: print(a,ev[j])
        if d == -1:
            if a:
                are_non_solo=1
            a.add(i)
        else:
            a.remove(i)
            if j +1 < 2 * n and ev[j+1][0] != t:
                if len(a) == 1 and ev[j+1][1] == -1:
                    if debug: print ('ą')
                    for nn in a:
                        count[nn] += 1
                if len(a) == 0:
                    brks += 1

    print(max(count) + brks+are_non_solo)


import sys
 
# inf = open('input.txt', 'r')
# reader = (line.rstrip() for line in inf)
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
 
t = int(input())
for _ in range(t):
    n = int(input())
    edges = []
    for i in range(n):
        li, ri = list(map(int, input().split()))
        edges.append((li, 0, i))
        edges.append((ri, 1, i))
    edges.sort()
    ctr = [0] * n
    opened = set()
    segmCtr = 0
    for k, (e, isEnd, i) in enumerate(edges):
        if isEnd:
            opened.remove(i)
            if not opened and edges[k-1][2] == i:
                ctr[i] -= 1
            elif len(opened) == 1 and edges[k+1][1] == 0:
                for j in opened:
                    ctr[j] += 1
        else:
            if not opened:
                segmCtr += 1
            opened.add(i)
    print(segmCtr + max(ctr))

# inf.close()


from sys import stdin
input = stdin.readline
q = int(input())
for rwere in range(q):
	n = int(input())
	seg = []
	pts = []
	for i in range(n):
		pocz, kon = map(int,input().split())
		seg.append([2*pocz, 2*kon])
		pts.append(2*kon+1)
	p,k = map(list,zip(*seg))
	pts += (p + k)
	pts.sort()
	ind = -1
	while True:
		if pts[ind] == pts[-1]:
			ind -= 1
		else:
			break
	ind += 1
	pts = pts[:ind]
	mapa = {}
	val = 0
	mapa[pts[0]] = val
	for i in range(1, len(pts)):
		if pts[i] != pts[i-1]:
			val += 1
		mapa[pts[i]] = val
	val += 1
	for i in range(n):
		seg[i] = [mapa[seg[i][0]], mapa[seg[i][1]]]
	seg.sort()
	dupa = [0] * (val+1)
	for s in seg:
		dupa[s[0]] += 1
		dupa[s[1] + 1] -= 1
	cov = [0] * val
	cov[0] = dupa[0]
	for i in range(1, val):
		cov[i] = cov[i-1] + dupa[i]
	przyn = [0] * val
	cur = seg[0][0]
	label = 1
	for i in range(n):
		kon = seg[i][1]
		if cur <= kon:
			for j in range(cur, kon + 1):
				przyn[j] = label
			label += 1
			cur = kon + 1
	final = [(przyn[i] if cov[i] == 1 else (-1 if cov[i] == 0 else 0)) for i in range(val)]
	baza = final.count(-1) + 1
	final = [-1] + final + [-1]
	val += 2
	if max(final) <= 0:
		print(baza)
	else:
		comp = {}
		comp[0] = -100000000000
		for i in final:
			if i > 0:
				comp[i] = 0
		for i in range(1, val - 1):
			if final[i] > 0 and final[i] != final[i-1]:
				comp[final[i]] += 1
			if final[i-1] == -1:
				comp[final[i]] -= 1
			if final[i+1] == -1:
				comp[final[i]] -= 1
		best = -10000000000000
		for i in comp:
			best = max(best, comp[i])
		if max(final) == n:
			print(baza + best)
		else:
			print(max(baza + best, baza))