Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chefina is playing with ranges. There are $N$ ranges $[l_{1}, r_{1}], [l_{2}, r_{2}], \ldots, [l_{N}, r_{N}]$. Chefina wants to divide the ranges into two non-empty subsets in such a way that each range is in exactly one subset and whenever two ranges have a common point, they are in the same subset.

Since this could be difficult to achieve, Chefina can delete any number of ranges (possibly zero) and then divide the remaining ranges into such non-empty subsets. She wants to know whether it is possible to achieve her task after deleting some ranges and if it is possible, she also wants to know the minimum number of ranges she needs to delete to achieve it.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.  
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains two space-separated integers $l_{i}$ and $r_{i}$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum number of ranges to delete, or $-1$ if it is impossible to delete some ranges and divide the remaining ranges into two non-empty subsets.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ l_{i} ≤ r_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (10 points): $N = 16$

Subtask #2 (15 points): $N = 1,000$

Subtask #3 (15 points): $r_{i} ≤ 10^{6}$ for each valid $i$

Subtask #4 (60 points): original constraints

----- Sample Input 1 ------ 
3

3

1 4

2 6

5 7

2

1 4

4 6

2

3 7

8 9
----- Sample Output 1 ------ 
1

-1

0
----- explanation 1 ------ 
Example case 1: It is enough to delete the range $[2, 6]$.

Example case 2: There is no way to divide these two ranges into two suitable non-empty subsets and deleting any range obviously makes it impossible too.

Example case 3: There is no need to delete any ranges, we can just put one range into one subset and the other range into the other subset.

Difficulty: HARD
Tags: Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
from sys import stdin, stdout
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	l = []
	departure = cnt = 0
	ans = float('inf')
	for i in range(n):
		(arr, dep) = list(map(int, stdin.readline().split()))
		l += [[arr, 1], [dep, -1]]
	l.sort(key=lambda x: (x[0], -x[1]))
	for (pt, type) in l:
		cnt += type
		if type == 1:
			if departure:
				ans = min(ans, cnt - 1)
		else:
			departure = 1
	print(ans if ans != float('inf') else -1)


for _ in range(int(input())):
	(n, lisa, lisb, curr, ans, i, j) = (int(input()), [], [], 0, 10000000.0, 0, 0)
	for _ in range(n):
		(a, b) = map(int, input().split())
		(lisa.append(a), lisb.append(b + 1))
	(lisa.sort(), lisb.sort())
	while i < n:
		if lisa[i] < lisb[j]:
			(curr, i) = (curr + 1, i + 1)
		else:
			(curr, j) = (curr - 1, j + 1)
		if curr != i:
			ans = min(ans, curr)
	print(-1) if ans == 10000000.0 else print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	ranges = []
	first = (0, 10 ** 9)
	last = (-1, 0)
	for _ in range(n):
		(l, r) = map(int, input().split())
		ranges.append((l, r))
		if r < first[1]:
			first = (l, r)
		if l > last[0]:
			last = (l, r)
	if first[1] >= last[0]:
		print(-1)
		continue
	vals = {}
	for tpl in ranges:
		(l, r) = tpl
		vals[l] = vals.get(l, 0) + 1
		vals[l + 0.5] = vals.get(l + 0.5, 0)
		vals[r + 0.5] = vals.get(r + 0.5, 0) - 1
	points = []
	for point in vals.keys():
		points.append(point)
	points.sort()
	points.pop()
	mincount = 10 ** 9
	count = 0
	for point in points:
		count += vals[point]
		if point > first[1] and point < last[0]:
			mincount = min(mincount, count)
		if mincount == 0:
			break
	print(mincount)


T = int(input())
for _ in range(T):
	N = int(input())
	begin = []
	end = []
	for iterations in range(N):
		l = [int(i) for i in input().split()]
		begin.append(l[0])
		end.append(l[1])
	begin = sorted(begin)
	end = sorted(end)
	array = [-1] * (2 * N)
	begin_index = 0
	end_index = 0
	k = 0
	count = 0
	while end_index < N and begin_index < N:
		if begin[begin_index] > end[end_index]:
			count -= 1
			array[k] = ['-', count]
			end_index += 1
		else:
			count += 1
			array[k] = ['+', count]
			begin_index += 1
		k += 1
	while begin_index < N:
		count += 1
		array[k] = ['+', count]
		begin_index += 1
		k += 1
	while end_index < N:
		count -= 1
		array[k] = ['-', count]
		end_index += 1
		k += 1
	result = float('inf')
	temp = 0
	for item in array:
		if item[0] == '-':
			temp = 1
		elif item[0] == '+':
			if temp:
				result = min(result, item[1] - 1)
	if result == float('inf'):
		print(-1)
	else:
		print(result)


for _ in range(int(input())):
	n = int(input())
	(l, r) = ([], [])
	for _ in range(n):
		(x, y) = map(int, input().strip().split())
		l.append(x)
		r.append(y)
	l.sort()
	r.sort()
	(ans, b, j) = (float('Inf'), False, 0)
	for i in range(n):
		while l[j] <= r[i]:
			j += 1
			if j == n:
				b = True
				break
		if b:
			break
		ans = min(ans, j - i - 1)
	print(-1 if ans == float('Inf') else ans)


T = int(input())
while T:
	N = int(input())
	arrive = []
	depart = []
	for i in range(N):
		(u, v) = map(int, input().split())
		arrive.append(u)
		depart.append(v)
	depart.sort()
	arrive.sort()
	List = [-1] * 2 * N
	(i, j, k) = (0, 0, 0)
	prev = 0
	while i < N and j < N:
		if arrive[i] > depart[j]:
			prev -= 1
			List[k] = ['d', prev]
			j += 1
		else:
			prev += 1
			List[k] = ['a', prev]
			i += 1
		k += 1
	while i < N:
		prev += 1
		List[k] = ['a', prev]
		i += 1
		k += 1
	while j < N:
		prev -= 1
		List[k] = ['d', prev]
		j += 1
		k += 1
	count = 10 ** 7
	flag = False
	for (u, v) in List:
		if u == 'a':
			if flag:
				count = min(count, v - 1)
		else:
			flag = True
	if count == 10 ** 7:
		print(-1)
	else:
		print(count)
	T -= 1


for _ in range(int(input())):
	N = int(input())
	(X, Y) = ([], [])
	for i in range(N):
		(H, Z) = map(int, input().split())
		X.append([H, 0])
		X.append([Z, 1])
	X.sort()
	M = float('inf')
	count = 0
	a = 0
	for i in range(len(X)):
		if a == N:
			break
		if X[i][1] == 0:
			count += 1
			a += 1
		else:
			count -= 1
			if count < M:
				M = count
	if M < N - 1:
		print(M)
	else:
		print('-1')


import bisect
for _ in range(int(input())):
	n = int(input())
	arr = []
	dep = []
	for i in range(n):
		(l1, r1) = map(int, input().split())
		arr.append(l1)
		dep.append(r1)
	arr.sort()
	dep.sort()
	mini = 10 ** 6
	merger = []
	count = 0
	a = 0
	d = 0
	while len(merger) != 2 * n:
		if arr[a] <= dep[d]:
			count += 1
			merger.append([count, 'a'])
			a += 1
			if a >= len(arr):
				arr.append(10 ** 9 + 1)
		else:
			count -= 1
			merger.append([count, 'd'])
			d += 1
			if d >= len(dep):
				dep.append(10 ** 9 + 1)
	f = 0
	for (i, j) in merger:
		if j == 'a':
			if f:
				mini = min(mini, i - 1)
		if j == 'd':
			f = 1
	if mini == 10 ** 6:
		mini = -1
	print(mini)


import functools
for _ in range(int(input())):
	x = int(input())
	start = []
	end = []
	min_end = float('inf')
	max_start = float('-inf')
	for i in range(x):
		(m, n) = map(int, input().split())
		if n < min_end:
			min_end = n
		if m > max_start:
			max_start = m
		start.append(m)
		end.append(n)
	if min_end >= max_start:
		print(-1)
	else:
		ar = []
		for (i, j) in zip(start, end):
			ar.append([i, 1])
			ar.append([j, -1])
		ar.sort(key=lambda x: x[1], reverse=True)
		ar.sort(key=lambda x: x[0])
		en = x
		i = len(ar) - 1
		while ar[i][1] != 1 and i >= 0:
			i -= 1
		en = i
		res = float('inf')
		s = i = 0
		flg = False
		while i < len(ar):
			s += int(ar[i][1])
			if ar[i][1] == -1:
				flg = True
			if flg and i < en:
				res = min(s, res)
			i += 1
		if res == float('inf'):
			print(-1)
		else:
			print(res)


from collections import defaultdict as t
for _ in range(int(input())):
	n = int(input())
	pt = set()
	(s, e) = (t(int), t(int))
	for i in range(n):
		(a, b) = map(int, input().split())
		pt.add(a)
		pt.add(b)
		s[a] += 1
		e[b] += 1
	l = 0
	ans = 10 ** 10
	se = 0
	pt = sorted(pt)
	for i in pt:
		l += s[i]
		l -= e[i]
		se += e[i]
		if se and n - l - se >= 1:
			ans = min(ans, l)
	if ans == 10 ** 10:
		print(-1)
	else:
		print(ans)


try:
	import sys
	t = int(input())
	for _ in range(t):
		l = []
		r = []
		arr = []
		n = int(input())
		for i in range(n):
			(a, b) = map(int, input().split())
			l.append(a)
			r.append(b)
		l.sort()
		r.sort()
		overlap = 1
		result = 1
		i = 1
		j = 0
		while i < n and j < n:
			if l[i] <= r[j]:
				overlap += 1
				i += 1
			else:
				overlap -= 1
				j += 1
			arr.append(overlap)
			if overlap == 0:
				result = 0
				break
			elif overlap == n:
				result = -1
				break
		a = sys.maxsize
		if result != 0 and result != -1:
			i = 0
			while i <= len(arr) - 3:
				if arr[i] == arr[i + 2]:
					if a > arr[i + 1]:
						a = arr[i + 1]
				i += 1
			print(a)
		else:
			print(result)
except:
	pass


def main(debug=False):
	for _ in range(int(input())):
		n = int(input())
		(l, r) = ([], [])
		for i in range(n):
			lr = list(map(int, input().split()))
			l.append(lr[0])
			r.append(lr[1])
		l.sort()
		r.sort()
		if debug:
			print(l)
			print(r)
		(lp, rp, mp) = (0, 0, 0)
		merged = [0 for i in range(2 * n)]
		if debug:
			print(merged)
		cnt = 0
		while True:
			if mp == 2 * n:
				break
			if lp == n:
				merged[mp:] = [cnt - (i - rp + 1) for i in range(rp, n)]
				break
			if rp == n:
				merged[mp:] = [cnt + (i - lp + 1) for i in range(lp, n)]
				break
			if debug:
				print('For i=', mp, 'l[lp] r[rp]', l[lp], r[rp])
			if l[lp] < r[rp]:
				cnt += 1
				merged[mp] = cnt
				lp += 1
			elif l[lp] == r[rp]:
				cnt += 1
				merged[mp] = cnt
				lp += 1
			elif l[lp] > r[rp]:
				cnt -= 1
				merged[mp] = cnt
				rp += 1
			mp += 1
		if debug:
			print(merged)
		prev = merged[0]
		flag = False
		count = 10 ** 5 + 1
		for i in range(1, 2 * n - 1):
			curr = merged[i]
			if curr > prev:
				if flag:
					count = min(count, merged[i] - 1)
			elif curr < prev:
				flag = True
			prev = curr
		if debug:
			print('Count', count)
		if count == 10 ** 5 + 1:
			print(-1)
		else:
			print(count)
main(debug=False)


def solve(l, r):
	l.sort()
	r.sort()
	overlap = 1
	n = len(l)
	arr = []
	(i, j) = (1, 0)
	while i < n and j < n:
		if l[i] <= r[j]:
			overlap += 1
			i += 1
		else:
			overlap -= 1
			j += 1
		arr.append(overlap)
		if overlap == 0:
			print(0)
			return
		if overlap == n:
			print(-1)
			return
	result = float('inf')
	for ind in range(len(arr) - 2):
		if arr[ind] == arr[ind + 2]:
			result = min(result, arr[ind + 1])
	print(result)
for case in range(int(input())):
	(l, r) = ([], [])
	for tp in range(int(input())):
		(a, b) = list(map(int, input().split()))
		l.append(a)
		r.append(b)
	solve(l, r)


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
from sys import stdin, stdout
from math import inf
from bisect import bisect_left

def solve():
	global n, pairs
	if n == 1:
		return -1
	begins = sorted([pair[0] for pair in pairs])
	ends = sorted([pair[1] for pair in pairs])
	mini = inf
	for (i, end) in enumerate(ends):
		p = bisect_left(begins, end + 1, lo=i)
		if n - p:
			mini = min(p - i - 1, mini)
	return mini if mini != inf else -1

def read_input():
	global n, pairs
	pairs = []
	n = int(input())
	for _ in range(n):
		(l, r) = map(int, stdin.readline().split())
		pairs.append((l, r))

def write_output(s):
	stdout.write('\n'.join(map(str, s)))

def main():
	s = []
	for _ in range(int(input())):
		read_input()
		answer = solve()
		s.append(answer)
	write_output(s)
main()


t = int(input())
while t > 0:
	n = int(input())
	arrival = []
	depart = []
	for i in range(n):
		arr = list(map(int, input().split()))
		arrival.append(arr[0])
		depart.append(arr[1])
	arrival.sort()
	depart.sort()
	merger = [[0, 'a'] for c in range(2 * n)]
	i = 0
	j = 0
	count = 0
	point = 0
	ans = 1000000
	while i < len(arrival) and j < len(depart):
		if arrival[i] <= depart[j]:
			count = count + 1
			merger[point][0] = count
			point = point + 1
			i = i + 1
		else:
			count = count - 1
			merger[point][0] = count
			merger[point][1] = 'd'
			point = point + 1
			j = j + 1
	while i < len(arrival):
		count = count + 1
		merger[point][0] = count
		point = point + 1
		i = i + 1
	while j < len(depart):
		count = count - 1
		merger[point][0] = count
		merger[point][1] = 'd'
		point = point + 1
		j = j + 1
	flag = False
	for (a, b) in merger:
		if b == 'a':
			if flag:
				ans = min(ans, a - 1)
				flag = True
		else:
			flag = True
	if ans == 1000000:
		print(-1)
	else:
		print(ans)
	t = t - 1


from sys import stdin
from collections import defaultdict
from bisect import bisect_right, insort
t = int(stdin.readline())
while t:
	n = int(stdin.readline())
	a = []
	for _ in range(n):
		(l, r) = map(int, stdin.readline().split())
		a.append((l, r))
	a.sort(key=lambda x: x[1])
	ans = 999999
	temp = [j[0] for j in a]
	temp.sort()
	for i in range(n - 1):
		v = bisect_right(temp, a[i][1])
		if v < len(temp):
			ans = min(ans, v - i - 1)
	if ans == 999999:
		ans = -1
	print(ans if n - ans >= 2 else '-1')
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	ends = []
	starts = []
	for _ in range(n):
		inp = list(map(int, input().split()))
		starts.append(inp[0])
		ends.append(inp[1])
	starts.sort()
	ends.sort()
	i = 0
	j = 0
	vals = []
	cnt = 999999999
	ctr = 0
	while i < n and j < n:
		if starts[i] > ends[j]:
			ctr -= 1
			j += 1
			cnt = min(cnt, ctr)
		else:
			i += 1
			ctr += 1
	if cnt == 999999999 or cnt == n:
		print(-1)
	else:
		print(cnt)
	t -= 1


T = int(input())
while T > 0:
	N = int(input())
	res = N
	count = 0
	l = []
	r = []
	for _ in range(N):
		(t1, t2) = list(map(int, input().split()))
		l.append(t1)
		r.append(t2)
	l = sorted(l)
	r = sorted(r)
	for _ in range(N):
		if l[_] > r[0]:
			count = _
			break
	else:
		print(-1)
		T -= 1
		continue
	(result, i, j) = (0, count, 0)
	while True:
		if l[i] <= r[j]:
			count += 1
			i += 1
			if i == N:
				break
		else:
			count -= 1
			res = min(res, count)
			j += 1
	print(res)
	T -= 1


import numpy as np
i8 = np.int64

def solve(l, r, n):
	res = n
	for i in range(n):
		if l[i] > r[0]:
			count = i
			break
	else:
		return -1
	il = count
	ir = 0
	while True:
		if l[il] <= r[ir]:
			count += 1
			il += 1
			if il == n:
				break
		else:
			count -= 1
			res = min(res, count)
			ir += 1
	return res

def main():
	f = open(0, 'r')
	stdin = np.fromstring(f.read(), i8, sep=' ')
	T = stdin[0]
	i = 1
	for _ in range(T):
		N = stdin[i]
		lr = stdin[i + 1:i + 1 + 2 * N].reshape(-1, 2).T
		l = lr[0]
		l = np.sort(l)
		r = lr[1]
		r = np.sort(r)
		print(solve(l, r, N))
		i += 2 * N + 1
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	end = []
	count1 = []
	for i in range(n):
		(a, b) = map(int, input().split())
		arr.append(a)
		end.append(b)
	arr.sort()
	end.sort()
	p1 = p2 = 0
	pre = 0
	while p1 != n and p2 != n:
		if arr[p1] <= end[p2]:
			if pre == 0:
				count1.append((1, 'a'))
			else:
				(x, y) = count1[pre - 1]
				count1.append((x + 1, 'a'))
			pre += 1
			p1 += 1
		else:
			(x, y) = count1[pre - 1]
			count1.append((x - 1, 'd'))
			pre += 1
			p2 += 1
	while p2 != n:
		(x, y) = count1[pre - 1]
		count1.append((x - 1, 'd'))
		pre += 1
		p2 += 1
	ans = 10000000
	flag = False
	for (i, j) in count1:
		if j == 'a':
			if flag:
				ans = min(ans, i - 1)
		else:
			flag = True
	if ans == 10000000:
		print('-1')
	else:
		print(ans)


from sys import stdin
from collections import defaultdict
test = int(stdin.readline())
MAX = 1000000001
for _ in range(test):
	N = int(stdin.readline())
	if N == 1:
		(a, b) = map(int, stdin.readline())
		print(-1)
		continue
	if N == 2:
		(a1, a2) = map(int, stdin.readline().split())
		(b1, b2) = map(int, stdin.readline().split())
		if a2 > b2:
			if b2 >= a1:
				print(-1)
			else:
				print(0)
		elif a2 == b2:
			print(-1)
		elif a2 >= b1:
			print(-1)
		else:
			print(0)
		continue
	entry = defaultdict(int)
	end = defaultdict(int)
	s = set()
	for i in range(N):
		(l, r) = map(int, stdin.readline().strip().split())
		s.add(l)
		s.add(r)
		entry[l] += 1
		end[r] += 1
	s = list(s)
	s.sort()
	ans = -1
	cnt = 0
	for i in range(len(s) - 1):
		cnt += entry[s[i]] - end[s[i]]
		if end[s[i]] > 0:
			if entry[s[i + 1]] > 0:
				if ans == -1:
					ans = cnt
				else:
					ans = min(ans, cnt)
	if ans == -1:
		print(-1)
	else:
		print(ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = []
	r = []
	arr = []
	for i in range(n):
		(l1, l2) = map(int, input().split())
		l.append(l1)
		r.append(l2)
	l.sort()
	r.sort()
	res = 1
	overlapping = 1
	i = 1
	j = 0
	while i < n and j < n:
		if l[i] <= r[j]:
			overlapping += 1
			i += 1
		else:
			overlapping -= 1
			j += 1
		arr.append(overlapping)
		if overlapping == 0:
			res = 0
			break
		if overlapping == n:
			res = -1
			break
	if res != 0 and res != -1:
		m = -1
		for i in range(len(arr) - 2):
			if arr[i] == arr[i + 2]:
				if m == -1:
					m = arr[i + 1]
				else:
					m = min(m, arr[i + 1])
		print(m)
	else:
		print(res)


T = int(input())
for t in range(T):
	n = int(input())
	ranges = []
	for i in range(n):
		(a, b) = map(int, input().split())
		ranges.append((a, 0))
		ranges.append((b, 1))
	ranges = list(sorted(ranges))
	cnt = 0
	res = 1000000000.0
	possible = False
	for (_, dir) in ranges:
		if dir == 0:
			if possible:
				res = min(res, cnt)
			cnt += 1
		else:
			cnt -= 1
			possible = True
	if res == 1000000000.0:
		res = -1
	print(res)


for _ in range(int(input())):
	n = int(input())
	(a, b) = ([], [])
	for i in range(n):
		(l, r) = map(int, input().split())
		a.append(l)
		b.append(r)
	temp = []
	a.sort(reverse=True)
	b.sort(reverse=True)
	count = 0
	while a and b:
		if a[-1] <= b[-1]:
			count += 1
			temp.append([count, 'a'])
			a.pop()
		else:
			count -= 1
			temp.append([count, 'd'])
			b.pop()
	while a:
		count += 1
		temp.append([count, 'a'])
		a.pop()
	while b:
		count -= 1
		temp.append([count, 'd'])
		b.pop()
	flag = False
	ans = 100000000
	for (i, j) in temp:
		if j == 'a':
			if flag:
				ans = min(ans, i - 1)
		else:
			flag = True
	if ans == 100000000:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	l = []
	r = []
	for i in range(n):
		(li, ri) = map(int, input().split())
		l.append(li)
		r.append(ri)
	l.sort()
	r.sort()
	(exists, flag) = (False, False)
	j = 0
	ans = n
	for i in range(n - 1):
		while l[j] <= r[i]:
			j += 1
			if j == n:
				flag = True
				break
		if flag == True:
			break
		ans = min(ans, j - i - 1)
		exists = True
	if exists == True:
		print(ans)
	else:
		print(-1)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(l, r) = map(int, input().split())
		a.append(l)
		b.append(r)
	a.sort()
	b.sort()
	(i, j) = (0, 0)
	cur = 0
	ans = 2 << 32
	while i < n and j < n:
		if a[i] <= b[j]:
			cur += 1
			i += 1
		else:
			cur -= 1
			j += 1
		if j > 0:
			ans = min(ans, cur)
	if ans == 2 << 32:
		print(-1)
	else:
		print(ans)


from collections import defaultdict as dd
for _ in range(int(input())):
	app = dd(int)
	dep = dd(int)
	all_set = set()
	n = int(input())
	for __ in range(n):
		(i, j) = input().strip().split()
		(i, j) = (int(i), int(j))
		app[i] += 1
		dep[j] += 1
		all_set.add(i)
		all_set.add(j)
	all_set = sorted(all_set)
	curr = 0
	min1 = float('inf')
	flag = 0
	for t in all_set:
		if flag == 0:
			if t in dep:
				flag = 1
		elif app[t] != 0:
			min1 = min(curr, min1)
		curr += app[t] - dep[t]
	if min1 == n - 1 or min1 == float('inf'):
		min1 = -1
	print(min1)


from collections import defaultdict

def checkdisjoint(a, b):
	if a[1] < b[0] or b[1] < a[0]:
		return True
	else:
		return False
for _ in range(int(input())):
	N = int(input())
	R = []
	FirstCloser = (0, 10000000000)
	LastOpener = (-1, 0)
	for k in range(N):
		(a, b) = map(int, input().split())
		if b < FirstCloser[1]:
			FirstCloser = (a, b)
		if a > LastOpener[0]:
			LastOpener = (a, b)
		R.append((a, b))
	if checkdisjoint(FirstCloser, LastOpener) == False:
		print('-1')
		continue
	d = defaultdict(int)
	for x in R:
		d[x[0]] += 1
		d[x[1] + 0.5] -= 1
	Points = []
	for x in d:
		Points.append(x)
	Points = sorted(Points)
	m = 10000000000
	s = 0
	Points.pop()
	for x in Points:
		s = s + d[x]
		if x > FirstCloser[1] and x < LastOpener[0]:
			m = min(m, s)
		if m == 0:
			break
		if x == LastOpener[0]:
			break
	print(m)


from sys import stdin, stdout
import bisect

def add(arr, N, lo, hi, val):
	arr[lo] += val
	if hi != N - 1:
		arr[hi + 1] -= val

def updateArray(arr, N):
	for i in range(1, N):
		arr[i] += arr[i - 1]
for i in range(int(stdin.readline())):
	n = int(stdin.readline())
	l = [0] * n
	l1 = []
	l2 = []
	for j in range(n):
		l1.append(list(map(int, stdin.readline().split())))
	l1.sort()
	for i in l1:
		l2.append(i[0])
	for i in range(n - 1):
		j = bisect.bisect(l2, l1[i][1])
		add(l, n, i + 1, j - 1, 1)
	updateArray(l, n)
	c = 10 ** 5 + 1
	for i in range(n):
		if l[i] < c and l[i] != i:
			c = l[i]
		if c == 0:
			break
	if c == 10 ** 5 + 1:
		print(-1)
		continue
	print(c)


test = int(input())
for intnt in range(test):
	num = int(input())
	arr1 = []
	arr2 = []
	for indx1 in range(num):
		(val1, y) = list(map(int, input().split()))
		arr1.append(val1)
		arr2.append(y)
	arr1.sort()
	arr2.sort()
	ar = []
	for i in range(num):
		ar.append(i)
	if num != 1:
		val1 = list(set(arr2))
		val1.sort()
		p = [0] * len(val1)
		q = [0] * len(val1)
		indx2 = 0
		indx1 = 0
		while indx1 < num:
			if indx2 == len(val1):
				break
			if arr1[indx1] <= val1[indx2]:
				p[indx2] += 1
				indx1 += 1
			else:
				indx2 += 1
		indx2 = 0
		indx1 = 0
		while indx1 < num:
			if indx2 == len(val1):
				break
			if arr2[indx1] <= val1[indx2]:
				q[indx2] += 1
				indx1 += 1
			else:
				indx2 += 1
				q[indx2] = q[indx2 - 1]
		for indx1 in range(1, len(p)):
			p[indx1] += p[indx1 - 1]
		for indx1 in range(len(p)):
			p[indx1] = num - p[indx1]
		ans = num + 2
		for indx1 in range(len(val1)):
			if not (p[indx1] == 0 or q[indx1] == 0):
				ans = min(ans, num - p[indx1] - q[indx1])
		if ans == num + 2:
			print(-1)
		else:
			print(ans)
	else:
		print(-1)


t = int(input())
for i in range(t):
	start = []
	end = []
	n = int(input())
	for j in range(n):
		inp = list(map(int, input().split()))
		start.append(inp[0])
		end.append(inp[1])
	cum_end = []
	cum_start = []
	from collections import Counter
	c = Counter(start)
	d = Counter(end)
	k = 0
	l = 0
	start_list = list(c.keys())
	end_list = list(d.keys())
	start_list.sort()
	end_list.sort()
	for item in start_list:
		k += c[item]
		cum_start.append(k)
	for item in end_list:
		l += d[item]
		cum_end.append(l)
	mini = 9999999999
	x = 0
	y = 0
	flag = 0
	while x < len(end_list) and y < len(start_list):
		a = cum_end[x]
		while start_list[y] <= end_list[x]:
			y += 1
			if y == len(start_list):
				flag = 1
				break
		if flag == 1:
			break
		else:
			b = l - cum_start[y - 1]
			if b == 0:
				break
			elif n - a - b < mini:
				mini = n - a - b
		x += 1
	if mini == 9999999999:
		print(-1)
	else:
		print(mini)


from sys import stdin

def search2(array, s, end):
	i = s
	j = len(array) - 1 - s
	while j > 0:
		while i + j < len(array) and array[i + j] <= end:
			i += j
		j //= 2
	if i == len(array) - 1:
		if array[len(array) - 1] < end:
			i += 1
	return i
for __ in range(int(stdin.readline())):
	starts = []
	ends = []
	n = int(stdin.readline())
	for i in range(n):
		(start, end) = map(int, stdin.readline().split())
		starts.append(start)
		ends.append(end)
	starts.sort()
	ends.sort()
	ans = 1010101
	e = s = 0
	while e < n and s < n:
		while s < n and starts[s] <= ends[e]:
			s += 1
		if s - e > 0 and s - e < ans and (s < n):
			ans = s - e
		e += 1
	if ans == 1010101:
		ans = 0
	print(ans - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	A = []
	for i in range(n):
		(l, r) = list(map(int, input().split()))
		A.append((l, 0))
		A.append((r, 1))
	A = sorted(A)
	minimumIntervals = float('inf')
	currentIntervals = 0
	lLeft = n
	foundR = False
	for (i, (l, r)) in enumerate(A[:-1]):
		if r == 0:
			currentIntervals += 1
			lLeft -= 1
		else:
			foundR = True
			currentIntervals -= 1
		if not foundR:
			continue
		if lLeft == 0:
			continue
		if currentIntervals < minimumIntervals:
			minimumIntervals = currentIntervals
	if minimumIntervals == float('inf'):
		print(-1)
	else:
		print(minimumIntervals)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	d = {}
	b = set()
	lm = 0
	rm = 1000000001
	mn = n
	while n > 0:
		n -= 1
		(l, r) = list(map(int, input().split()))
		if l not in d:
			d[l] = 0
		if r + 1 not in d:
			d[r + 1] = 0
		if r not in d:
			d[r] = 0
		d[l] += 1
		d[r + 1] -= 1
		b.add(l)
		b.add(r)
		if rm > r:
			rm = r
		if lm < l:
			lm = l
	if rm >= lm:
		print(-1)
	else:
		b1 = list(b)
		b1.sort()
		p = 0
		f = 0
		for i in range(len(b1) - 1):
			p = p + d[b1[i]] + f
			if b1[i] >= rm and b1[i] <= lm:
				if p < mn:
					mn = p
				if p == 1:
					break
			if b1[i] + 1 in d and b1[i] + 1 != b1[i + 1]:
				f = d[b1[i] + 1]
			else:
				f = 0
		print(mn - 1)


from functools import cmp_to_key
import sys
VALUE = 0
DIR = 1

def sort_cmp(a, b):
	if a[VALUE] != b[VALUE]:
		return 1 if a[VALUE] > b[VALUE] else -1
	return -1 if a[DIR] else 1

def key_func(x):
	d = 0 if x[DIR] else 0.5
	return x[VALUE] + d

def optimized():
	n = int(input())
	ranges = []
	for i in range(n):
		(l, r) = input().split()
		(l, r) = (int(l), int(r))
		ranges.append([l, True])
		ranges.append([r, False])
	ranges = sorted(ranges, key=key_func)
	rem = n - 1
	covered = 0
	over = 1
	ans = sys.maxsize
	for i in range(1, len(ranges)):
		if ranges[i][VALUE] != ranges[i - 1][VALUE]:
			if covered > 0 and rem > 0:
				ans = min(ans, over)
		if ans == 0:
			break
		if ranges[i][DIR]:
			rem -= 1
			over += 1
		else:
			over -= 1
			covered += 1
	if ans == sys.maxsize:
		ans = -1
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		optimized()
main()


import math
import bisect
import sys
input = sys.stdin.readline

def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def inn():
	return int(input())

def inl():
	return list(map(int, input().split()))
MOD = 10 ** 9 + 7
INF = inf = 10 ** 18 + 5
for t in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(inl())
	lmax = -INF
	rmin = INF
	for i in arr:
		lmax = max(lmax, i[0])
		rmin = min(rmin, i[1])
	if rmin >= lmax or n == 1:
		print(-1)
		continue
	arr.sort()
	if n == 2:
		if arr[0][1] < arr[1][0]:
			print(0)
		else:
			print(-1)
		continue
	pos = {}
	for i in arr:
		pos[i[0]] = 0
		pos[i[1]] = 0
	for i in arr:
		pos[i[0]] += 1
		pos[i[1]] -= 1
	k = list(pos.keys())
	k.sort()
	for i in range(1, len(k)):
		pos[k[i]] += pos[k[i - 1]]
	ans = INF
	for i in range(len(k)):
		if k[i] < rmin:
			continue
		if k[i] >= lmax:
			break
		ans = min(ans, pos[k[i]])
	print(ans)


def fun(partitions):
	if len(partitions) == 2:
		print(0)
	else:
		end_points = {}
		for j in partitions:
			end_points[j[0]] = end_points.get(j[0], 0) + 1
			end_points[j[1]] = end_points.get(j[1], 0) - 1
		final_partitions = sorted(end_points.items())
		temp = []
		temp.append(0)
		for j in final_partitions:
			temp.append(temp[-1] + j[1])
		if len(temp) > 4:
			a = min(temp[2:-2])
		else:
			a = min(temp[1:-1])
		if a >= len(partitions) - 1:
			print(-1)
		else:
			print(a)
t = int(input())
for i in range(t):
	n = int(input())
	ans = n
	maxl0 = int(0)
	minl1 = int(0)
	partitions = {}
	for j in range(n):
		l = input().split(' ')
		l[0] = int(l[0])
		l[1] = int(l[1])
		partitions[l[0]] = partitions.get(l[0], 0) + 1
		partitions[l[1]] = partitions.get(l[1], 0) - 1
		if j == 0:
			maxl0 = l[0]
			minl1 = l[1]
		else:
			maxl0 = max(maxl0, l[0])
			minl1 = min(minl1, l[1])
	sorted_partitions = []
	for j in sorted(partitions.keys()):
		sorted_partitions.append([j, partitions[j]])
	cnt = int(0)
	for j in sorted_partitions:
		cnt += j[1]
		if cnt < ans and j[0] >= minl1 and (j[0] < maxl0):
			ans = cnt
	if ans > n - 2:
		print(-1)
	else:
		print(ans)


from bisect import bisect_left, bisect_right
T = int(input())
for t in range(T):
	lefts = list()
	rights = list()
	N = int(input())
	for i in range(N):
		(l, r) = map(int, input().split())
		lefts.append(l)
		rights.append(r)
	lefts.sort()
	rights.sort()
	found = False
	minDropped = int(1000000000.0)
	for r in rights:
		leftLen = bisect_right(rights, r)
		rightLen = N - bisect_left(lefts, r + 1)
		if rightLen > 0:
			found = True
			minDropped = min(minDropped, N - (leftLen + rightLen))
	if found:
		print(minDropped)
	else:
		print(-1)


n_of_test_cases = input()
n_of_test_cases = int(n_of_test_cases)
for test_cases in range(n_of_test_cases):
	begin = []
	end = []
	for iterations in range(int(input())):
		l = [int(i) for i in input().split()]
		begin.append(l[0])
		end.append(l[1])
	size = len(begin)
	begin = sorted(begin)
	end = sorted(end)
	array = [-1] * (2 * size)
	begin_index = 0
	end_index = 0
	k = 0
	count = 0
	while end_index < size and begin_index < size:
		if begin[begin_index] > end[end_index]:
			count -= 1
			array[k] = ['-', count]
			end_index += 1
		else:
			count += 1
			array[k] = ['+', count]
			begin_index += 1
		k += 1
	while begin_index < size:
		count += 1
		array[k] = ['+', count]
		begin_index += 1
		k += 1
	while end_index < size:
		count -= 1
		array[k] = ['-', count]
		end_index += 1
		k += 1
	result = float('inf')
	temp = 0
	for item in array:
		if item[0] == '-':
			temp = 1
		elif item[0] == '+':
			if temp:
				result = min(result, item[1] - 1)
	if result == float('inf'):
		print(-1)
	else:
		print(result)


for _ in range(int(input())):
	arr = []
	dep = []
	pair = []
	n = int(input())
	for _ in range(n):
		(a, d) = input().split()
		pair.append((int(a), int(d)))
		arr.append(int(a))
		dep.append(int(d))
	arr.sort()
	dep.sort()
	i = 0
	j = 0
	count = 0
	plat = []
	while i < n and j < n:
		if arr[i] <= dep[j]:
			count += 1
			plat.append((count, 'a'))
			i += 1
		elif arr[i] > dep[j]:
			count -= 1
			plat.append((count, 'd'))
			j += 1
	while i < n:
		count += 1
		plat.append((count, 'a'))
		i += 1
	while j < n:
		count -= 1
		plat.append((count, 'd'))
		j += 1
	flag = False
	ans = 1000000
	for (cnt, typ) in plat:
		if typ == 'a':
			if flag:
				ans = min(ans, cnt - 1)
		else:
			flag = True
	if ans == 1000000:
		ans = -1
	print(ans)


def main():
	nn = rem = cnt = a = b = i = temp = 0
	for _ in range(int(input())):
		vec = []
		nn = int(input())
		rem = cnt = 0
		res = nn
		for i in range(nn):
			(a, b) = input().split()
			vec.append([int(a), 1])
			vec.append([int(b), 0])
		vec.sort()
		i = 0
		while i < len(vec) - 1:
			j = i
			while j < len(vec) and vec[j][0] == vec[i][0]:
				if vec[j][1] == 1:
					cnt += 1
				else:
					cnt -= 1
					rem += 1
				j += 1
			i = j
			temp = nn - rem - cnt
			if temp != 0 and rem != 0:
				if res > cnt:
					res = cnt
		if res == nn:
			res = -1
		print(res)
main()


for _ in range(int(input())):
	n = int(input())
	d = {}
	inter = []
	laststart = 0
	firstend = 1000000000
	for i in range(n):
		(l, r) = input().split()
		l = int(l)
		r = int(r)
		if l > laststart:
			laststart = l
		if firstend > r:
			firstend = r
		if l in d.keys():
			d[l][0] += 1
		else:
			d[l] = [1, 0]
		if r in d.keys():
			d[r][1] += 1
		else:
			d[r] = [0, 1]
	k = sorted(list(d.keys()))
	flag = 0
	temp = 0
	for i in k:
		if i == laststart:
			break
		if flag == 0:
			temp += d[i][0] - d[i][1]
			if i == firstend and d[i][1] != 0:
				inter.append(temp)
				flag = 1
		elif flag == 1:
			temp += d[i][0] - d[i][1]
			inter.append(temp)
	if len(inter) == 0:
		print(-1)
	else:
		inter = sorted(inter)
		print(inter[0])


def testcase(arr, dep, n):
	arr.sort()
	dep.sort()
	plat_needed = 0
	result = n
	i = 0
	j = 0
	flag = False
	while i < n and j < n - 1:
		if arr[i] <= dep[j]:
			plat_needed += 1
			i += 1
		else:
			flag = True
			plat_needed -= 1
			j += 1
		if plat_needed < result and flag:
			result = plat_needed
		if result == 0:
			return 0
	if n - result < 2:
		return -1
	if result > n - 1:
		return -1
	return result

def testcase2(n, pair):
	counter = len(pair)
	for current in range(len(pair)):
		flag = True
		count = 0
		upper = pair[current][1]
		for i in range(len(pair)):
			if i == current:
				continue
			if pair[i][1] <= upper:
				continue
			if pair[i][1] > upper:
				if pair[i][0] > upper:
					flag = False
					continue
				else:
					count += 1
		if flag:
			count = len(pair)
		counter = min(counter, count)
	if counter >= n - 1:
		return -1
	else:
		return counter
t = int(input())
for i in range(t):
	n = int(input())
	arr = []
	dep = []
	for j in range(n):
		(a, b) = [int(_) for _ in input().split()]
		arr.append(a)
		dep.append(b)
	print(testcase(arr, dep, n))


for t in range(int(input())):
	n = int(input())
	(starts, ends) = ([], [])
	(minimum, maximum) = (float('inf'), 0)
	for i in range(n):
		t = [int(i) for i in input().split()]
		starts.append(t[0])
		ends.append(t[1])
	starts.sort()
	ends.sort()
	(counts, startI) = ({}, 0)
	for (i, end) in enumerate(ends):
		end += 0.5
		while startI < n and starts[startI] < end:
			startI += 1
		endBef = i + 1
		counts[end] = (startI, endBef)
	best = None
	for (pt, (startBef, endBef)) in counts.items():
		contains = startBef - endBef
		if startBef != n and startBef != 0 and (best == None or contains < best):
			best = contains
	if best == None:
		print(-1)
	else:
		print(best)


def binary(a, l, r, e):
	if e > a[r] or l > r:
		return -1
	(start, end, mid, max1) = (l, r, -1, -1)
	while start <= end:
		mid = start + end >> 1
		if a[mid] > e:
			end = mid - 1
		else:
			start = mid + 1
			max1 = max(mid, max1)
	return max1
for _ in range(int(input())):
	n = int(input())
	tr = {}
	arr = [0 for i in range(n)]
	for i in range(n):
		(l, r) = [int(i) for i in input().split(' ')]
		tr[l] = tr.get(l, 0) + 1
		arr[i] = r
	arr.sort()
	(last, count, ans) = (0, 0, n)
	for k in sorted(tr.keys()):
		last = max(binary(arr, last, n - 1, k - 1) + 1, last)
		delete = count - last
		if delete != count:
			ans = min(ans, delete)
		if ans == 0:
			break
		count += tr[k]
	if ans != n:
		print(ans)
	else:
		print(-1)


from collections import defaultdict

def solve(lr, N):
	levels = defaultdict(lambda : [0, 0])
	for (l, r) in lr:
		levels[l][1] += 1
		levels[r][0] -= 1
	levels = [(key, val1, val2) for (key, (val1, val2)) in levels.items()]
	levels.sort()
	level = 0
	min_level = N
	started = False
	for (p, l, r) in levels:
		if r > 0 and started:
			if level < min_level:
				min_level = level
			started = False
		if l < 0:
			started = True
		level += l + r
	if min_level == N:
		min_level = -1
	return min_level
T = int(input())
for t in range(T):
	N = int(input())
	lr = [tuple(map(int, input().split())) for _ in range(N)]
	lr.sort()
	result = solve(lr, N)
	print(result)


t = int(input())
for i in range(t):
	n = int(input())
	start = []
	end = []
	for i in range(n):
		s = list(map(int, input().split()))
		start.append(s[0])
		end.append(s[1])
	s = e = ps = pe = 0
	start.sort()
	end.sort()
	a = start[0]
	b = start[n - 1]
	c = end[0]
	d = end[n - 1]
	m = n
	if b <= c:
		m = -1
	else:
		while pe == 0:
			if start[ps] < end[pe]:
				tmp = start[ps]
				s += 1
				ps += 1
				while ps < n and start[ps] == tmp:
					s += 1
					ps += 1
			elif start[ps] == end[pe]:
				tmp = start[ps]
				e += 1
				pe += 1
				s += 1
				ps += 1
				while ps < n and start[ps] == tmp:
					s += 1
					ps += 1
				while pe < n and end[pe] == tmp:
					e += 1
					pe += 1
			else:
				tmp = end[pe]
				e += 1
				pe += 1
				while pe < n and end[pe] == tmp:
					e += 1
					pe += 1
		while ps < n and pe < n:
			if s - e < m:
				m = s - e
			if start[ps] < end[pe]:
				s += 1
				ps += 1
			elif start[ps] == end[pe]:
				s += 1
				ps += 1
				e += 1
				pe += 1
			else:
				e += 1
				pe += 1
	print(m)


import math
import random
from collections import defaultdict

def type1():
	return map(int, input().split())

def type2():
	return list(type1())

def type3():
	return int(input())

def solve2(l, r, n):
	l.sort()
	r.sort()
	noofends = 0
	noofstarts = n
	i = 0
	j = 0
	ans = 999999999999
	while (i < n and j < n) and i + j < 2 * n:
		if l[i] < r[j]:
			limit = l[i]
			while i < n and l[i] == limit:
				i += 1
				noofstarts -= 1
			if noofends > 0 and noofstarts > 0:
				ans = min(ans, n - (noofends + noofstarts))
		elif l[i] > r[j]:
			limit = r[j]
			while j < n and r[j] == limit:
				j += 1
				noofends += 1
			if noofends > 0 and noofstarts > 0:
				ans = min(ans, n - (noofends + noofstarts))
		else:
			limit = l[i]
			temp = noofstarts
			while i < n and l[i] == limit:
				i += 1
				noofstarts -= 1
			if noofends > 0 and noofstarts > 0:
				ans = min(ans, n - (noofends + noofstarts))
			limit = r[j]
			while j < n and r[j] == limit:
				j += 1
				noofends += 1
			if noofends > 0 and noofstarts > 0:
				ans = min(ans, n - (noofends + noofstarts))
	return -1 if ans == 999999999999 else ans
for _ in range(type3()):
	n = type3()
	left = []
	right = []
	for i in range(n):
		(l, r) = type1()
		left.append(l)
		right.append(r)
	print(solve2(left, right, n))


import math
import random
from collections import defaultdict

def type1():
	return map(int, input().split())

def type2():
	return list(type1())

def type3():
	return int(input())

def solve(l, r, n):
	if n == 1:
		return -1
	if n == 2:
		l = sorted(l)
		r = sorted(r)
		if l[1] > r[0]:
			return 0
		else:
			return -1
	if n > 2:
		sortedright = sorted(list(set(r)))
		sortedleft = sorted(list(set(l)))
		if sortedright >= 2 or sortedleft >= 2:
			secmin = sortedleft[1]
			secmax = sortedright[-2]
			prefix = [0] * (sortedright[-1] + 2)
			edges = [[0, 0] for i in range(sortedright[-1] + 2)]
			for i in range(n):
				prefix[l[i]] += 1
				prefix[r[i] + 1] -= 1
				edges[l[i]][0] += 1
				edges[r[i]][1] += 1
			print(prefix, secmin, secmax)
			for i in range(sortedleft[0], sortedright[-1] + 1):
				prefix[i] += prefix[i - 1]
			print(prefix)
			ans = 9999999999
			for i in range(secmin, secmax + 1):
				ans = min(ans, prefix[i])
			print(ans)
			fans = 9999999999
			print(edges)
			for i in range(secmin, secmax + 1):
				if prefix[i] == ans:
					fans = min(ans, ans - edges[i][0], ans - edges[i][1])
			print(fans)
			fans = -1 if n - 2 < fans else fans
			return fans
		else:
			return -1

def solve1(l, r, n):
	start = min(l)
	end = max(r)
	prefix = [0] * (end + 2)
	edges = [[0, 0] for i in range(end + 2)]
	for i in range(n):
		prefix[l[i]] += 1
		prefix[r[i] + 1] -= 1
		edges[l[i]][0] += 1
		edges[r[i]][1] += 1
	for i in range(start, end + 1):
		prefix[i] += prefix[i - 1]
	nstarts = n
	nends = 0
	ans = 99999999999
	for i in range(start, end + 1):
		nstarts -= edges[i][0]
		nends += edges[i][1]
		if nstarts > 0 and nends > 0:
			ans = min(prefix[i] - edges[i][0], prefix[i] - edges[i][1])
	ans = -1 if ans == 99999999999 else ans
	return ans

def solve2(l, r, n):
	l.sort()
	r.sort()
	noofends = 0
	noofstarts = n
	i = 0
	j = 0
	ans = 999999999999
	while (i < n and j < n) and i + j < 2 * n:
		if l[i] < r[j]:
			limit = l[i]
			while i < n and l[i] == limit:
				i += 1
				noofstarts -= 1
			if noofends > 0 and noofstarts > 0:
				ans = min(ans, n - (noofends + noofstarts))
		elif l[i] > r[j]:
			limit = r[j]
			while j < n and r[j] == limit:
				j += 1
				noofends += 1
			if noofends > 0 and noofstarts > 0:
				ans = min(ans, n - (noofends + noofstarts))
		else:
			limit = l[i]
			temp = noofstarts
			while i < n and l[i] == limit:
				i += 1
				noofstarts -= 1
			if noofends > 0 and noofstarts > 0:
				ans = min(ans, n - (noofends + noofstarts))
			limit = r[j]
			while j < n and r[j] == limit:
				j += 1
				noofends += 1
			if noofends > 0 and noofstarts > 0:
				ans = min(ans, n - (noofends + noofstarts))
	return -1 if ans == 999999999999 else ans
for _ in range(type3()):
	n = type3()
	left = []
	right = []
	for i in range(n):
		(l, r) = type1()
		left.append(l)
		right.append(r)
	print(solve2(left, right, n))


try:
	testcase = int(input())
	while testcase:
		testcase -= 1
		n = int(input())
		(mi, ma1) = (10 ** 9 + 9, 10 ** 9 + 9)
		(ma, mi1) = (0, 0)
		(l, d) = ({}, {})
		for i in range(0, n):
			(x, y) = map(int, input().split())
			l.setdefault(x, 0)
			l.setdefault(y + 1, 0)
			d.setdefault(x, 0)
			l[x] += 1
			l[y + 1] -= 1
			d[x] += 1
			mi = min(mi, x)
			mi1 = max(mi1, x)
			ma = max(ma, y)
			ma1 = min(ma1, y)
		o = sorted(l.items(), key=lambda t: t[0])
		sp = 0
		c = {}
		for i in o:
			sp += i[1]
			if i[0] >= ma1 + 1 and i[0] < mi1 + 1 and (i[0] in d):
				c[i[0]] = sp
		an = 10 ** 9 + 6
		for (x, y) in c.items():
			an = min(c[x] - d[x], an)
		print(-1 if n - an <= 1 else an)
except:
	pass


from sys import *

def input():
	return stdin.readline()
import collections
for _ in range(int(input())):
	stp = collections.defaultdict(int)
	edp = collections.defaultdict(int)
	lis = []
	seg = []
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		stp[x] += 1
		edp[y] += 1
	com = stp.keys() & edp.keys()
	for i in com:
		seg.append([i, stp[i], edp[i]])
	for i in stp.keys() - com:
		seg.append([i, stp[i], 0])
	for i in edp.keys() - com:
		seg.append([i, 0, edp[i]])
	seg.sort(key=lambda x: x[0])
	st = seg[0]
	curr = st[1] - st[2]
	unable = 0
	res = 9999999
	if st[2] == 0:
		firseg = True
	else:
		firseg = False
	step = 1
	while firseg and step < len(seg):
		if seg[step][2] > 0:
			firseg = False
		unable += curr
		curr = seg[step][1] - seg[step][2]
		step += 1
	while step < len(seg):
		unable += curr
		if seg[step][1] > 0:
			res = min(res, unable)
		curr = seg[step][1] - seg[step][2]
		step += 1
	if res == 9999999:
		print(-1)
	else:
		print(res)


import bisect

def result(l1, l2, num):
	res = num
	for nex in range(1, num):
		inter = num - bisect.bisect_right(l1, l2[nex - 1])
		if inter > 0:
			inter = num - inter - nex
			if res > inter:
				res = inter
			continue
	if res > num - 2:
		return -1
	return res
T = int(input())
while T:
	T -= 1
	N = int(input())
	if N == 1:
		print(-1)
	else:
		leftRanges = []
		rightRanges = []
		for i in range(0, N):
			(a, b) = map(int, input().split())
			leftRanges.append(a)
			rightRanges.append(b)
		print(result(sorted(leftRanges), sorted(rightRanges), N))


t = int(input())
for _ in range(t):
	n = int(input())
	s = []
	e = []
	for i in range(n):
		(l, r) = map(int, input().strip().split(' '))
		s.append(l)
		e.append(r)
	s.sort()
	e.sort()
	i = 0
	j = 0
	mi = float('inf')
	for i in range(1, n):
		while e[j] < s[i]:
			j += 1
		if j == 0:
			continue
		mi = min(i - j, mi)
	if mi == float('inf'):
		print(-1)
	else:
		print(mi)


T = int(input())
for _ in range(T):
	N = int(input())
	A = []
	B = []
	C = []
	(a, b) = map(int, input().split())
	mb = b
	xb = b
	ma = a
	xa = a
	A.append([a, b])
	B.append(a)
	C.append(b)
	for i in range(N - 1):
		(a, b) = map(int, input().split())
		if b < mb:
			mb = b
		if b > xb:
			xb = b
		if a < ma:
			ma = a
		if a > xa:
			xa = a
		A.append([a, b])
		B.append(a)
		C.append(b)
	if xa <= mb:
		print(-1)
		continue
	maxval = N - 1
	B.sort(reverse=True)
	C.sort(reverse=True)
	count = 0
	i = len(B) - 1
	j = len(C) - 1
	while True:
		if i == -1:
			break
		if B[i] <= C[j]:
			count = count + 1
			if B[i] > mb:
				maxval = min(count - 1, maxval)
			i = i - 1
		else:
			count = count - 1
			j = j - 1
	print(maxval)


for t in range(int(input())):
	n = int(input())
	d = dict()
	for _ in range(n):
		(x, y) = map(int, input().split())
		if x in d:
			d[x][0] += 1
		else:
			d[x] = [1, 0, 0]
		if y in d:
			d[y][1] += 1
		else:
			d[y] = [0, 1, 0]
	o = 0
	c = 0
	ans = n + 1
	for i in sorted(d):
		o += d[i][0]
		c += d[i][1]
		d[i][2] = o - c
		if c == 0 or o == n:
			continue
		ans = min(ans, d[i][2])
	if n - ans > 1:
		print(ans)
	else:
		print('-1')


import bisect
for _ in range(int(input())):
	n = int(input())
	(l, r) = (list(), list())
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append(a)
		r.append(b)
	l.sort()
	r.sort()
	ans = pow(10, 9) + 1
	for i in range(1, n):
		temp = n - bisect.bisect_right(l, r[i - 1])
		if temp:
			ans = min(ans, n - temp - i)
	if ans > n:
		print(-1)
	else:
		print(ans)


def compare(a, b):
	if a[0] < b[0]:
		return -1
	elif a[0] == b[0]:
		if a[1] == b[1]:
			return -1
		if a[1] < b[1]:
			return 1
		else:
			return -1
	else:
		return 1
import functools

def test4(start, end, x):
	ar = []
	start.sort()
	end.sort()
	for (i, j) in zip(start, end):
		ar.append([i, 1])
		ar.append([j, -1])
	ar.sort(key=lambda x: x[1], reverse=True)
	ar.sort(key=lambda x: x[0])
	en = x
	i = len(ar) - 1
	while ar[i][1] != 1 and i >= 0:
		i -= 1
	en = i
	res = float('inf')
	s = 0
	i = 0
	flg = False
	while i < len(ar):
		s += int(ar[i][1])
		if ar[i][1] == -1:
			flg = True
		if flg and i < en:
			res = min(s, res)
		i += 1
	if res == float('inf'):
		print(-1)
	else:
		print(res)
t = int(input())
while t:
	t -= 1
	p = int(input())
	(start, end) = ([], [])
	min_end = float('inf')
	max_start = float('-inf')
	for i in range(p):
		(m, n) = map(int, input().split())
		if n < min_end:
			min_end = n
		if m > max_start:
			max_start = m
		start.append(m)
		end.append(n)
	if min_end >= max_start:
		print(-1)
	else:
		test4(start, end, p)


import itertools
for _ in range(0, int(input())):
	n = int(input())
	l = {}
	d = {}
	mi = 10 ** 9 + 4
	ma = 0
	mi1 = 0
	ma1 = 10 ** 9 + 4
	for i in range(0, n):
		(x, y) = map(int, input().split())
		if x in l:
			l[x] += 1
		else:
			l[x] = 1
		if y + 1 in l:
			l[y + 1] -= 1
		else:
			l[y + 1] = -1
		if x not in d:
			d[x] = 1
		else:
			d[x] += 1
		mi = min(mi, x)
		mi1 = max(mi1, x)
		ma = max(ma, y)
		ma1 = min(ma1, y)
	ans = 10 ** 9 + 6
	l = sorted(l.items(), key=lambda t: t[0])
	s = 0
	j = 0
	c = {}
	for i in range(0, len(l)):
		s += l[i][1]
		if l[i][0] >= ma1 + 1 and l[i][0] < mi1 + 1 and (l[i][0] in d):
			c[l[i][0]] = s
	for (u, v) in c.items():
		ans = min(c[u] - d[u], ans)
	if n - ans <= 1:
		print(-1)
	else:
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	ip = []
	for i in range(n):
		(a, b) = map(int, input().split())
		ip.append((a, 0))
		ip.append((b, 1))
	ip = sorted(ip)
	c = 0
	ans = n
	closed = 0
	for i in ip:
		if closed >= 1 and c != n - closed:
			ans = min(c, ans)
		if i[1] == 0:
			c += 1
		else:
			c -= 1
			closed += 1
	if ans == n or ans == n - 1:
		print(-1)
	else:
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		(l, r) = list(map(int, input().split()))
		a.append(l)
		b.append(r)
	a.sort()
	b.sort()
	if n == 1:
		print(-1)
	else:
		x = set(b)
		x = list(x)
		x.sort()
		p = [0] * len(x)
		q = [0] * len(x)
		j = 0
		i = 0
		while i < n:
			if j == len(x):
				break
			if b[i] <= x[j]:
				q[j] += 1
				i += 1
			else:
				j += 1
				q[j] = q[j - 1]
		j = 0
		i = 0
		while i < n:
			if j == len(x):
				break
			if a[i] <= x[j]:
				p[j] += 1
				i += 1
			else:
				j += 1
		for i in range(1, len(p)):
			p[i] += p[i - 1]
		for i in range(len(p)):
			p[i] = n - p[i]
		ans = 2 * n
		for i in range(len(x)):
			if not (p[i] == 0 or q[i] == 0):
				ans = min(ans, n - p[i] - q[i])
		if ans == 2 * n:
			print(-1)
		else:
			print(ans)


from bisect import *
from collections import *
from sys import *

def input():
	return stdin.readline()
for _ in range(int(input())):
	x1 = defaultdict(int)
	y1 = defaultdict(int)
	lis = []
	fin = []
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		x1[x] += 1
		y1[y] += 1
	inter = x1.keys() & y1.keys()
	for i in inter:
		fin.append([i, [x1[i], y1[i]]])
	intrax = x1.keys() - inter
	for i in intrax:
		fin.append([i, [x1[i], 0]])
	intray = y1.keys() - inter
	for i in intray:
		fin.append([i, [0, y1[i]]])
	fin.sort(key=lambda x: x[0])
	st = fin[0]
	tmp = st[1][0] - st[1][1]
	u = 0
	r = 999999999
	if st[1][1] == 0:
		subset = True
	else:
		subset = False
	it = 1
	while subset and it < len(fin):
		if fin[it][1][1] > 0:
			subset = False
		u += tmp
		tmp = fin[it][1][0] - fin[it][1][1]
		it += 1
	while it < len(fin):
		u += tmp
		if fin[it][1][0] > 0:
			r = min(r, u)
		tmp = fin[it][1][0] - fin[it][1][1]
		it += 1
	if r == 999999999:
		print(-1)
	else:
		print(r)


def main():
	t = int(input())
	for p in range(t):
		n = int(input())
		arr = []
		left_max = 0
		right_min = 10 ** 9
		for i in range(n):
			x = input().split()
			(x[0], x[1]) = (int(x[0]), int(x[1]))
			left_max = max(left_max, x[0])
			right_min = min(right_min, x[1])
			arr.append([x[0], 'L'])
			arr.append([x[1], 'R'])
		arr.sort()
		final_ans = 10 ** 5
		ans = 0
		for i in range(2 * n):
			if arr[i][1] == 'L':
				if arr[i][0] > right_min:
					final_ans = min(final_ans, ans)
				ans += 1
			else:
				ans -= 1
		if final_ans == 10 ** 5:
			print(-1)
		else:
			print(final_ans)
main()


def upper_bound(arr, x):
	(l, h) = (0, len(arr))
	while l < h:
		mid = (l + h) // 2
		if x >= arr[mid]:
			l = mid + 1
		else:
			h = mid
	return l

def main():
	for t in range(int(input())):
		n = int(input())
		XS = [0 for i in range(n)]
		YS = [0 for i in range(n)]
		for i in range(n):
			(a, b) = map(int, input().split())
			XS[i] = a
			YS[i] = b
		XS.sort()
		YS.sort()
		(res, i) = (n, 0)
		while i < n:
			it = i
			while it < n and YS[it] == YS[i]:
				it += 1
			idx = upper_bound(XS, YS[i])
			if it < n and idx < n:
				res = min(res, idx - it)
			i = it
		print(res if res != n else -1)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	s = []
	for i in range(n):
		(l, r) = input().split()
		l = int(l)
		r = int(r)
		s.append([l, r])
	s.sort()
	l = []
	l.append([s[0][0], s[0][1], 1])
	for i in range(1, n):
		if s[i][0] > l[-1][1]:
			l.append([s[i][0], s[i][1], 1])
		elif s[i][0] <= l[-1][1]:
			l[-1][1] = max(l[-1][1], s[i][1])
			l[-1][2] += 1
	if len(l) > 1:
		print(0)
	elif l[0][2] <= 2:
		print(-1)
	else:
		l2 = []
		for i in range(0, len(s)):
			l2.append(s[i][1])
		l2.sort()
		sp = 0
		ep = 0
		m = n + 1
		i = 0
		j = 0
		f = 0
		while i < n:
			if s[i][0] <= l2[j]:
				sp += 1
				if sp - 1 - ep < m and ep != 0:
					f = 1
					m = sp - ep - 1
				i += 1
			else:
				ep += 1
				j += 1
		if f == 1:
			print(m)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = []
	brr = []
	for i in range(n):
		(a, b) = map(int, input().split())
		x = min(a, b)
		y = max(a, b)
		arr.append([x, y])
		brr.append(y)
	arr.sort()
	curr_max = arr[0][1]
	ind = 0
	rs = []
	for i in range(1, n):
		if arr[i][0] > curr_max:
			rs.append(i - ind)
			ind = i
			curr_max = arr[i][1]
		elif arr[i][1] > curr_max:
			curr_max = arr[i][1]
	rs.append(n - ind)
	if len(rs) >= 2:
		print(0)
	else:
		brr.sort()
		i = 0
		j = 0
		result = -1
		while i < n and j < n:
			if arr[i][0] <= brr[j]:
				if i != 0 and j != 0:
					if result == -1:
						result = i - j
						rs_ind = i
					elif result > i - j:
						result = i - j
						rs_ind = i
				i += 1
			else:
				j += 1
		print(result)


for h in range(int(input())):
	beg = []
	end = []
	n = int(input())
	for _ in range(n):
		(s, e) = map(int, input().strip().split())
		beg.append(s)
		end.append(e)
	mini = float('inf')
	beg.sort()
	end.sort()
	(j1, j2) = (n - 1, n - 1)
	while beg[j1] == beg[j1 - 1] and j1 > 0:
		j1 -= 1
	while end[j2] == end[j2 - 1] and j2 > 0:
		j2 -= 1
	if j1 == 0 or j2 == 0:
		print(-1)
		continue
	c = 0
	(i1, i2) = (0, 0)
	while i1 < j1 and i2 < j2:
		if beg[i1] <= end[i2]:
			c += 1
			i1 += 1
		else:
			c -= 1
			i2 += 1
			mini = min(c, mini)
	while i2 < j2 and end[i2] < beg[j1]:
		c -= 1
		i2 += 1
		mini = min(c, mini)
	if mini == n or mini == float('inf'):
		print(-1)
	else:
		print(mini)


for _ in range(int(input())):
	n = int(input())
	xlis = []
	ylis = []
	for i in range(n):
		(a, b) = map(int, input().split())
		xlis.append(a)
		ylis.append(b)
	xlis.sort()
	ylis.sort()
	ans = 0
	poi = 0
	for i in range(n):
		y = ylis[i]
		while poi != n:
			if xlis[poi] <= y:
				poi += 1
			else:
				break
		gx = n - poi
		if gx == 0:
			break
		else:
			smly = i + 1
			ans = max(ans, smly + gx)
			fl = 1
	if ans:
		print(n - ans)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	li = []
	for j in range(n):
		(x, y) = map(int, input().split())
		li.append([x, 's'])
		li.append([y + 0.01, 'c'])
	li.sort(key=lambda x: x[0])
	mi = 1000000001
	l = 0
	pre = li[0]
	for i in range(1, len(li)):
		if li[i][1] == 's':
			l += 1
		elif li[i][1] == 'c':
			l -= 1
		if li[i][1] == 's' and pre[1] == 'c':
			mi = min(mi, l)
		pre = li[i]
	if mi == 1000000001:
		print(-1)
	else:
		print(mi)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	dic = defaultdict(lambda : 0)
	for i in range(n):
		(a, b) = [int(i) for i in input().split()]
		dic[a] += 1
		dic[b + 0.1] -= 1
	vals = sorted(list(dic.keys()))
	ans = 10 ** 10
	s = 0
	ans_arr = [-1]
	for val in vals:
		curr = dic[val]
		s += curr
		ans_arr.append(s)
	ans_arr.append(-1)
	for i in range(1, len(ans_arr) - 1):
		if ans_arr[i - 1] > ans_arr[i] and ans_arr[i + 1] > ans_arr[i]:
			ans = min(ans, ans_arr[i])
	if ans >= n - 1 or ans == 10 ** 9:
		print(-1)
	else:
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	ranges = {1: [0, 0, 0, 0]}
	for i in range(n):
		(l, r) = map(int, input().split())
		if l in ranges:
			ranges[l][0] += 1
		else:
			ranges[l] = [1, 0, 0, 0]
		if r in ranges:
			ranges[r][1] += 1
		else:
			ranges[r] = [0, 1, 0, 0]
	sortedkeys = sorted(ranges)
	opened = 0
	closed = 0
	for i in sortedkeys:
		opened += ranges[i][0]
		closed += ranges[i][1]
		opened -= ranges[i][1]
		ranges[i][2] = opened
		ranges[i][3] = closed
	sortedkeysDesc = sorted(ranges, reverse=True)
	flag = 0
	todelete = -1
	x = -1
	for j in sortedkeysDesc:
		if flag == 0 and ranges[j][0] >= 1:
			flag = 1
		elif flag == 1 and ranges[j][3] > 0:
			if ranges[j][2] < todelete or todelete == -1:
				todelete = ranges[j][2]
	print(todelete)


for _ in range(int(input())):
	n = int(input())
	start = []
	end = []
	for __ in range(n):
		(a, b) = map(int, input().split())
		start.append(a)
		end.append(b)
	start.sort()
	end.sort()
	s = {}
	e = {}
	su = 1
	en = 0
	k = 0
	for i in range(1, n):
		if start[i] > start[i - 1]:
			s[start[i]] = su
		su += 1
		while start[i] > end[k]:
			en += 1
			k += 1
		e[start[i]] = k
	ans = 1000000007
	for i in s.keys():
		if i > end[0]:
			t = s[i] - e[i]
			if ans > t:
				ans = t
	if ans == 1000000007:
		print(-1)
	else:
		print(ans)


for _ in range(int(input())):
	N = int(input())
	li = []
	for i in range(N):
		(a, b) = [int(j) for j in input().split()]
		li.append((a, 0))
		li.append((b, 1))
	li.sort()
	r = len(li) - 1
	while li[r][1] == 1:
		r -= 1
	flag = -1
	curr = -1
	mn = N
	for (ind, i) in enumerate(li):
		if curr == 0:
			flag = 1
			break
		elif curr == N:
			flag = 2
			break
		elif curr == -1:
			curr = 0
		if i[1] == 0:
			curr += 1
		else:
			curr -= 1
			if ind <= r + 1:
				mn = min(curr, mn)
	if flag == -1:
		print(mn)
	elif flag == 1:
		print(0)
	else:
		print(-1)