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: HARD
Tags: Graph algorithms

Constructive algorithms

Sorting

Amortized analysis

Complete search

Tree algorithms

Dynamic programming

Data structures
Skill types: Sorting

Amortized analysis

Complete search

Dynamic programming

Data structures

Starter code:

Solutions:
from sys import stdin
input = stdin.buffer.readline
t = int(input())
while t:
	t -= 1
	n = int(input())
	seg = []
	for i in range(n):
		(l, r) = map(int, input().split())
		seg.append((l, 0, i))
		seg.append((r, 1, i))
	seg.sort()
	ans = 0
	seq = []
	active = set()
	increase = [0] * -~n
	for (pos, p, i) in seg:
		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))
	if max(seq) == 1:
		print(ans - 1)
	else:
		print(ans + max(increase))


import sys
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))


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


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
	while atE < n:
		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 io
import os
from collections import Counter, defaultdict, deque

class SegmentTree:

	def __init__(self, data, default=0, func=max):
		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):
		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)

def merge(x, y):
	(xClose, xFull, xOpen) = x
	(yClose, yFull, yOpen) = y
	if xOpen == yClose:
		if xOpen:
			ret = (xClose, xFull + 1 + yFull, yOpen)
		else:
			ret = (xClose, xFull + yFull, yOpen)
	elif xOpen > yClose:
		ret = (xClose, xFull, xOpen - yClose + yOpen)
	elif xOpen < yClose:
		ret = (xClose + yClose - xOpen, yFull, yOpen)
	return ret

def solve(N, segments):
	endpoints = []
	for (i, (l, r)) in enumerate(segments):
		endpoints.append((l, 0, i))
		endpoints.append((r, 1, i))
	endpoints.sort()
	data = []
	idToIndices = defaultdict(list)
	for (x, kind, segmentId) in endpoints:
		if kind == 0:
			data.append((0, 0, 1))
		else:
			assert kind == 1
			data.append((1, 0, 0))
		idToIndices[segmentId].append(len(data) - 1)
	assert len(data) == 2 * N
	segTree = SegmentTree(data, (0, 0, 0), merge)
	best = 0
	for (k, indices) in idToIndices.items():
		assert len(indices) == 2
		removed = []
		for i in indices:
			removed.append(segTree[i])
			segTree[i] = (0, 0, 0)
		res = segTree.query(0, 2 * N)
		assert res[0] == 0
		assert res[2] == 0
		best = max(best, res[1])
		for (i, old) in zip(indices, removed):
			segTree[i] = old
	return best
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()]
	segments = [[int(x) for x in input().split()] for i in range(N)]
	ans = solve(N, segments)
	print(ans)


def solve(lsts):
	points = []
	for i in range(len(lsts)):
		points.append((lst[i][0], 0, i))
		points.append((lst[i][1], 1, i))
	points.sort()
	open = set()
	increased = [0] * len(lsts)
	original = 0
	for i in range(len(points)):
		p = points[i]
		if p[1] == 0:
			open.add(p[2])
		else:
			open.remove(p[2])
		if len(open) == 1 and p[1] == 1 and (points[i + 1][1] == 0):
			increased[list(open)[0]] += 1
		if len(open) == 1 and p[1] == 0 and (points[i + 1][1] == 1):
			increased[list(open)[0]] -= 1
		if len(open) == 0:
			original += 1
	res = -float('inf')
	for i in range(len(lsts)):
		res = max(res, increased[i])
	return res + original
n = int(input())
for _ in range(n):
	m = int(input())
	lst = []
	for _ in range(m):
		lst.append(list(map(int, input().split())))
	print(solve(lst))


import io
import os
from collections import Counter, defaultdict, deque

class SegmentTree:

	def __init__(self, data, default=0, func=max):
		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):
		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)

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

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

def merge(x, y):
	(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)
	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])
	data = []
	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)
	best = 0
	for (intervalId, indices) in idToIndices.items():
		(i, j) = indices
		(removed1, removed2) = (segTree[i], segTree[j])
		(segTree[i], segTree[j]) = (pack(0, 0, 0), pack(0, 0, 0))
		res = unpack(segTree.query(0, 2 * N))
		assert res[0] == 0
		assert res[2] == 0
		best = max(best, res[1])
		(segTree[i], segTree[j]) = (removed1, removed2)
	return best
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)


import sys
from math import gcd

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

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

def mints():
	return 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()
	s = set()
	p = None
	start = None
	px = int(-2000000000.0 - 5)
	pt = -1
	pp = px
	segs = []
	for i in range(0, 2 * n):
		(x, t, id) = a[i]
		if 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(2000000000.0 + 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) = 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
input = sys.stdin.readline
from itertools import accumulate
import random
t = int(input())
for testcases in range(t):
	n = int(input())
	S = [list(map(int, input().split())) for i in range(n)]
	compression_list = []
	for (l, r) in S:
		compression_list.append(l)
		compression_list.append(r)
	compression_dict = {a: ind for (ind, a) in enumerate(sorted(set(compression_list)))}
	for i in range(n):
		S[i][0] = compression_dict[S[i][0]] * 2
		S[i][1] = compression_dict[S[i][1]] * 2
	LEN = len(compression_dict) * 2
	R = [0] * (LEN + 1)
	for (l, r) in S:
		R[l] += 1
		R[r + 1] -= 1
	SR = list(accumulate(R))
	NOW = 0
	for i in range(LEN):
		if SR[i] != 0 and SR[i + 1] == 0:
			NOW += 1
	ONECOUNT = [0] * (LEN + 1)
	for i in range(1, LEN):
		if SR[i - 1] != 1 and SR[i] == 1:
			ONECOUNT[i] += 1
	SO = list(accumulate(ONECOUNT))
	SO.append(0)
	ANS = 1
	for (l, r) in S:
		lr = 0
		if SR[r] == 1:
			lr -= 1
		ANS = max(ANS, NOW + SO[r - 1] - SO[l] + lr)
	print(ANS)


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
input = sys.stdin.readline
t = int(input())
for testcases in range(t):
	n = int(input())
	S = [tuple(map(int, input().split())) for i in range(n)]
	S.sort()
	S.append((1 << 31, 1 << 31))
	seg_el = 1 << n.bit_length()
	SEG = [1 << 30] * (2 * seg_el)

	def update(n, x, seg_el):
		i = n + seg_el
		SEG[i] = x
		i >>= 1
		while i != 0:
			SEG[i] = min(SEG[i * 2], SEG[i * 2 + 1])
			i >>= 1

	def getvalues(l, r):
		L = l + seg_el
		R = r + seg_el
		ANS = 1 << 30
		while L < R:
			if L & 1:
				ANS = min(ANS, SEG[L])
				L += 1
			if R & 1:
				R -= 1
				ANS = min(ANS, SEG[R])
			L >>= 1
			R >>= 1
		return ANS
	LEFT = [0] * n
	MAX = -1 << 31
	MAXLIST = []
	for i in range(n):
		if MAX < S[i][0]:
			LEFT[i] = LEFT[i - 1] + 1
		else:
			LEFT[i] = LEFT[i - 1]
		MAX = max(MAX, S[i][1])
		MAXLIST.append(MAX)
	RIGHT = [0] * (n + 1)
	RIGHT[n - 1] = 1
	update(n - 1, 1, seg_el)
	update(n, 0, seg_el)
	import bisect
	for i in range(n - 2, -1, -1):
		(l, r) = S[i]
		if l == S[i + 1][0]:
			RIGHT[i] = RIGHT[i + 1]
		else:
			x = bisect.bisect_left(S, (r, -1 << 31))
			if x < i + 1:
				x = i + 1
			if r == S[x][0]:
				RIGHT[i] = getvalues(i + 1, x + 1)
			else:
				RIGHT[i] = min(getvalues(i + 1, x), RIGHT[x] + 1)
		update(i, RIGHT[i], seg_el)
	ANS = max(RIGHT[1], LEFT[-2])
	for i in range(1, n - 1):
		if S[i][0] == S[i + 1][0] or (S[i][0] != S[i - 1][0] and S[i][1] <= MAXLIST[i - 1]):
			continue
		x = bisect.bisect_left(S, (MAXLIST[i - 1], -1 << 31))
		if x < i + 1:
			x = i + 1
		if MAXLIST[i - 1] == S[x][0]:
			ANS = max(ANS, LEFT[i - 1] + getvalues(i + 1, x + 1) - 1)
		else:
			ANS = max(ANS, LEFT[i - 1] + min(getvalues(i + 1, x) - 1, RIGHT[x]))
	print(ANS)


import io
import os
from collections import defaultdict

class SegmentTree:

	def __init__(self, data, default=0, func=max):
		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):
		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 Node:

	def __init__(self, numClose, count, numOpen):
		self.close = numClose
		self.count = count
		self.open = numOpen
neutral = Node(0, 0, 0)

def combine(x, y):
	if x.open == y.close == 0:
		ret = (x.close, x.count + y.count, y.open)
	elif x.open == y.close:
		ret = (x.close, x.count + 1 + y.count, y.open)
	elif x.open > y.close:
		ret = (x.close, x.count, x.open - y.close + y.open)
	elif x.open < y.close:
		ret = (x.close + y.close - x.open, y.count, y.open)
	return Node(*ret)

def solve(N, intervals):
	OPEN = 0
	CLOSE = 1
	endpoints = []
	for (i, (l, r)) in enumerate(intervals):
		endpoints.append((l, OPEN, i))
		endpoints.append((r, CLOSE, i))
	endpoints.sort(key=lambda t: t[1])
	endpoints.sort(key=lambda t: t[0])
	data = []
	idToIndices = defaultdict(list)
	for (x, kind, intervalId) in endpoints:
		if kind == OPEN:
			data.append(Node(0, 0, 1))
		else:
			assert kind == CLOSE
			data.append(Node(1, 0, 0))
		idToIndices[intervalId].append(len(data) - 1)
	assert len(data) == 2 * N
	segTree = SegmentTree(data, Node(0, 0, 0), combine)
	best = 0
	for (intervalId, indices) in idToIndices.items():
		(i, j) = indices
		(removed1, removed2) = (segTree[i], segTree[j])
		(segTree[i], segTree[j]) = (neutral, neutral)
		res = segTree.query(0, 2 * N)
		assert res.open == 0
		assert res.close == 0
		best = max(best, res.count)
		(segTree[i], segTree[j]) = (removed1, removed2)
	return best
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)