Read problems statements in Mandarin Chinese  and Russian. 

N one dimensional kingdoms are represented as intervals of the form [a_{i} , b_{i}] on the real line.
A kingdom of the form [L, R] can be destroyed completely by placing a bomb at a point x on the real line if L 
≤ x ≤ R.

Your task is to determine minimum number of bombs required to destroy all the one dimensional kingdoms.

------ Input ------ 

First line of the input contains T denoting number of test cases.

For each test case, first line contains N denoting the number of one dimensional kingdoms.

For each next N lines, each line contains two space separated integers a_{i} and b_{i}.

------ Output ------ 

For each test case , output an integer denoting the minimum  number of bombs required.

------ Constraints ------ 

Subtask 1 (20 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 100 , 0 ≤ a_{i} ≤ b_{i} ≤500  
Subtask 2 (30 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 1000 , 0 ≤ a_{i} ≤ b_{i} ≤ 1000   
Subtask 3 (50 points) : 1 ≤ T ≤ 20 , 1 ≤ N ≤ 10^{5}, 0 ≤ a_{i} ≤ b_{i} ≤ 2000 

----- Sample Input 1 ------ 
1
3
1 3
2 5
6 9
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
There are three kingdoms [1,3] ,[2,5] and [6,9]. You will need at least 2 bombs 
to destroy the kingdoms. In one of the possible solutions, you can place two bombs at x = 2 and x = 6 .

Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		dictk = [-1] * 2001
		for o in range(n):
			(a, b) = map(int, input().split())
			dictk[b] = max(dictk[b], a)
		maxk = -1
		res = 0
		for i in range(0, 2001):
			if maxk < dictk[i]:
				res += 1
				maxk = i
		print(res)
except:
	pass


T = int(input())
for i in range(T):
	N = int(input())
	array = []
	for j in range(N):
		l = input()
		array.append([int(i) for i in l.split()])
	array = sorted(array)
	count = 1
	point = array[0][1]
	for j in range(1, N):
		if array[j][0] <= point:
			point = min(point, array[j][1])
		else:
			point = array[j][1]
			count += 1
	print(count)


import math
from math import log2, sqrt
import sys
from sys import stdin, stdout
import os
sys.setrecursionlimit(pow(10, 6))
import collections
from collections import defaultdict
from statistics import median
inf = float('inf')

def present(x, y, lista):
	return x <= lista[1] and y >= lista[0]

def get(x, y, lista):
	left = max(x, lista[0])
	right = min(y, lista[1])
	return [left, right]
t = int(input())
for i in range(t):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort()
	bombs = 1
	x = l[0][0]
	y = l[0][1]
	for i in range(1, len(l)):
		if present(x, y, l[i]):
			(x, y) = get(x, y, l[i])
		else:
			bombs += 1
			(x, y) = (l[i][0], l[i][1])
	print(bombs)


T = int(input())
for t in range(T):
	N = int(input())
	kingdoms = [[int(x) for x in input().split()] for n in range(N)]
	kingdoms.sort(key=lambda x: x[1])
	ans = 0
	newmax = -1
	for i in range(len(kingdoms)):
		if kingdoms[i][0] > newmax:
			ans += 1
			newmax = kingdoms[i][1]
	print(ans)


for _ in range(int(input())):
	N = int(input())
	a = []
	for i in range(N):
		a.append(list(map(int, input().split())))
	a.sort(key=lambda x: x[1])
	ans = 0
	k = -1
	for i in range(N):
		l = a[i][0]
		r = a[i][1]
		if l > k:
			ans += 1
			k = r
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	a.sort()
	m = 1
	x = a[0][1]
	for i in a[1:]:
		s = i[0]
		e = i[1]
		if s > x:
			m += 1
			x = e
		else:
			x = min(x, e)
	print(m)


def minBombs(kds):
	bombs = 0
	end = kds[0][1]
	for kd in kds[1:]:
		if kd[0] > end:
			bombs += 1
			end = kd[1]
		else:
			end = min(end, kd[1])
	bombs += 1
	return bombs
T = int(input())
for t in range(T):
	N = int(input())
	kds = []
	for n in range(N):
		(a, b) = map(int, input().split())
		kds.append([a, b])
	kds.sort(key=lambda kd: kd[0])
	print(minBombs(kds))


for _ in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		(d, b) = map(int, input().split())
		a.append([b, d])
	a.sort()
	c = 1
	if n == 1:
		print(1)
	f = a[0][0]
	for i in range(1, len(a)):
		if f < a[i][1]:
			c += 1
			f = a[i][0]
	print(c)


m = int(input())
for t in range(m):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	a.sort()
	c = 0
	temp = None
	for i in a:
		if temp is None:
			temp = i
		elif i[0] > temp[1]:
			c += 1
			temp = i
		elif i[1] < temp[1]:
			temp = i
		else:
			temp = [i[0], temp[1]]
	print(c + 1)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
	ans = 1
	l.sort(key=lambda x: x[1])
	last = l[0][1]
	for p in range(1, n):
		if l[p][0] > last:
			ans += 1
			last = l[p][1]
	print(ans)


def ss(l):
	n = len(l)
	l = sorted(l, key=lambda x: x[1])
	ans = 0
	b = -float('inf')
	for i in range(n):
		(x, y) = l[i]
		if x > b:
			ans += 1
			b = y
	return ans
for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	print(ss(l))


for _ in range(int(input())):
	n = int(input())
	l = []
	(a, r, c) = (0, 2000, 1)
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort()
	for k in l:
		if k[0] > r:
			c += 1
			(a, r) = k
		else:
			a = k[0]
			r = min(r, k[1])
	print(c)


def solve(intervals):
	intervals.sort(key=lambda x: x[1])
	cnt = 0
	stack = [intervals[0]]
	for i in range(1, len(intervals)):
		curr = intervals[i]
		if stack and curr[0] <= stack[-1][-1]:
			(ps, pe) = stack.pop()
			stack.append([max(ps, curr[0]), min(pe, curr[-1])])
		else:
			stack.append(curr)
	return len(stack)
for _ in range(int(input())):
	n = int(input())
	temp = []
	while n:
		temp.append(list(map(lambda x: int(x), input().split())))
		n -= 1
	print(solve(temp))


for _ in range(int(input())):
	k = []
	for _ in range(int(input())):
		k.append([int(i) for i in input().split()])
	k = sorted(k)
	last_val = k[0][1]
	count = 1
	for i in range(1, len(k)):
		if k[i][0] <= last_val:
			if k[i][1] < last_val:
				last_val = k[i][1]
		else:
			first_val = k[i][0]
			last_val = k[i][1]
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append((a, b))
	l.sort(key=lambda x: x[1])
	max_l = l[0][1]
	final_count = 1
	for ind in range(1, n):
		if l[ind][0] > max_l:
			final_count += 1
			max_l = l[ind][1]
	print(final_count)


for _ in range(int(input())):
	N = int(input())
	cnt = 0
	r = []
	for i in range(N):
		x = tuple(map(int, input().split()))
		r.append(x)
	r.sort(key=lambda x: x[1])
	k = -1
	for i in range(len(r)):
		if r[i][0] > k:
			cnt += 1
			k = r[i][1]
	print(cnt)


def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	k = n
	a = []
	bomb = 1
	for i in range(n):
		a.append(tuple(li()))
	a.sort(key=lambda x: x[1])
	fini = a[0][1]
	for i in range(1, n):
		if a[i][0] > fini:
			bomb += 1
			fini = a[i][1]
	print(bomb)


def main():
	t = int(input())
	while t:
		t -= 1
		n = int(input())
		a = []
		for i in range(n):
			temp = list(map(int, input().split()))
			a.append(temp)
		a.sort()
		bomb = 0
		i = 0
		while i < n:
			bomb += 1
			l_cur = a[i][0]
			h_cur = a[i][1]
			j = i + 1
			while j < n:
				if h_cur >= a[j][0]:
					l_cur = a[j][0]
					if a[j][1] < h_cur:
						h_cur = a[j][1]
					j += 1
				else:
					break
			i = j
		print(bomb)
main()


def min_bombs(interval):
	interval = sorted(interval)
	count = 0
	last = None
	for (start, end) in interval:
		if last is None:
			last = (start, end)
		elif start > last[1]:
			count += 1
			last = (start, end)
		elif end < last[1]:
			last = (start, end)
		else:
			last = (start, last[1])
	return count + 1
TestCases = int(input())
for t in range(TestCases):
	n = int(input())
	interval = []
	for i in range(n):
		interval.append([int(x) for x in input().split()])
	print(min_bombs(interval))


def cnt_bomb(arr):
	arr.sort()
	cnt = 0
	last = None
	for (st, end) in arr:
		if last is None:
			last = (st, end)
		elif st > last[1]:
			cnt += 1
			last = (st, end)
		elif end < last[1]:
			last = (st, end)
		else:
			last = (st, last[1])
	return cnt + 1
for t in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append([int(x) for x in input().split()])
	print(cnt_bomb(a))


for _ in range(int(input())):
	(p, q, r) = (0, 20000, 1)
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort()
	for i in l:
		if i[0] > q:
			r += 1
			(p, q) = i
		else:
			p = i[0]
			q = min(q, i[1])
	print(r)


for _ in range(int(input())):
	n = int(input())
	res = []
	for i in range(n):
		(a, b) = map(int, input().split())
		res.append([a, b])
	res = sorted(res, key=lambda x: x[1])
	(p, q) = (0, 100000)
	cont = 1
	for i in res:
		if i[0] > q:
			cont += 1
			(p, q) = i
		else:
			p = i[0]
			q = min(q, i[1])
	print(cont)


for _ in range(int(input())):
	n = int(input())
	res = []
	for i in range(n):
		(a, b) = map(int, input().split())
		res.append([a, b])
	res = sorted(res, key=lambda x: x[1])
	m = 10000000
	cont = 1
	for i in res:
		if i[0] > m:
			cont += 1
			m = i[1]
		else:
			m = min(m, i[1])
	print(cont)


for _ in range(int(input())):
	n = int(input())
	vp = []
	for i in range(n):
		(a, b) = map(int, input().split())
		vp.append((a, b))
	ans = 1
	vp.sort(key=lambda x: x[1])
	mx = vp[0][1]
	for it in range(1, n):
		if vp[it][0] > mx:
			ans += 1
			mx = vp[it][1]
	print(ans)


for t in range(0, int(input())):
	n = int(input())
	count = 0
	arr = []
	for i in range(0, n):
		(a, b) = map(int, input().split())
		arr.append([a, b])
	arr.sort(key=lambda x: x[1])
	k = -1
	for i in range(0, n):
		a = arr[i][0]
		b = arr[i][1]
		if a > k:
			count += 1
			k = b
	print(count)


def destryKingdoms():
	t = int(input())
	for _ in range(t):
		n = int(input())
		kingdoms = []
		for i in range(n):
			kingdoms.append(list(map(int, input().split())))
		kingdoms.sort(key=lambda x: (x[0], x[1]))
		r = kingdoms[0][1]
		count = 0
		for i in range(1, n):
			if kingdoms[i][0] > r:
				count += 1
				r = kingdoms[i][1]
			else:
				r = min(kingdoms[i][1], r)
		print(count + 1)
destryKingdoms()


def oneDimensionalKingdom(arr, n):
	arr.sort(key=lambda x: x[1])
	ans = 1
	last = arr[0][1]
	first = arr[0][0]
	for i in range(1, n):
		if arr[i][0] > last:
			ans += 1
			first = arr[i][0]
			last = arr[i][1]
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	print(oneDimensionalKingdom(arr, n))


for _ in range(int(input())):
	k = []
	for i in range(int(input())):
		k.append(list(map(int, input().split())))
	k.sort(key=lambda x: x[0], reverse=True)
	bomb = 1
	min = k[0][0]
	for j in range(1, len(k)):
		if min > k[j][1]:
			bomb += 1
			min = k[j][0]
	print(bomb)


def min_run(invs):
	interval = sorted(invs)
	counter = 1
	last = None
	for input_data_list in interval:
		start = input_data_list[0]
		end = input_data_list[1]
		if last == None:
			last = input_data_list
		elif start > last[1]:
			counter += 1
			last = (start, end)
		elif end < last[1]:
			last = (start, end)
		else:
			last = (start, last[1])
	return counter
testcases = int(input())
for i in range(testcases):
	input_len = int(input())
	intervals = []
	for j in range(input_len):
		intervals.append([int(x) for x in input().split()])
	res = min_run(intervals)
	print(res)


import sys, math
for _ in range(int(input())):
	n = int(input())
	arr = []
	for i in range(n):
		(a, b) = [int(c) for c in input().split()]
		arr.append((a, b))
	arr.sort(key=lambda x: x[1])
	endpoint = -1
	ans = 0
	for (a, b) in arr:
		if endpoint < a:
			endpoint = b
			ans += 1
	print(ans)


from math import *
from collections import *
from functools import *

def rvi():
	return [*map(int, input().split())]

def ri():
	return int(input())
for _ in range(ri()):
	n = ri()
	t = []
	for i in range(n):
		(a, b) = rvi()
		t += [(a, 0, i), (b, 1, i)]
	t.sort()
	r = 0
	i = 0
	entered_and_alive = [False] * n
	stack = []
	while i < len(t):
		(x, end, idx) = t[i]
		if not end:
			entered_and_alive[idx] = True
			stack.append(idx)
		elif entered_and_alive[idx]:
			r += 1
			for s in stack:
				entered_and_alive[s] = False
			stack = []
		else:
			pass
		i += 1
	print(r)


t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for _ in range(n):
		a.append(list(map(int, input().split())))
	a.sort()
	count = 1
	(f1, s1) = (a[0][0], a[0][1])
	for i in range(len(a)):
		if a[i][0] <= s1:
			f1 = a[i][0]
			s1 = min(s1, a[i][1])
		else:
			count += 1
			f1 = a[i][0]
			s1 = a[i][1]
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	l = []
	for z in range(n):
		(a, b) = map(int, input().split())
		l.append([a, b])
	l.sort(key=lambda x: x[1])
	c = 1
	first = l[0][1]
	for i in range(1, len(l)):
		if l[i][0] > first:
			c += 1
			first = l[i][1]
	print(c)


for z in range(int(input())):
	n = int(input())
	a = []
	for i in range(n):
		a.append([int(x) for x in input().split()])
	a.sort(key=lambda x: x[1])
	x = 1
	m = a[0][1]
	for i in range(1, n):
		if a[i][0] > m:
			m = a[i][1]
			x += 1
	print(x)


t = int(input())
for f in range(t):
	n = int(input())
	a = []
	x = 0
	y = 10000000
	count = 1
	for i in range(n):
		a.append(list(map(int, input().split())))
	a.sort()
	for k in a:
		if k[0] > y:
			count += 1
			y = k[1]
		else:
			y = min(k[1], y)
		x = k[0]
	print(count)


import math

def calc(data):
	data.sort(key=lambda x: x[1])
	bomb_location = -1
	bomb_count = 0
	for (a, b) in data:
		if a > bomb_location:
			bomb_location = b
			bomb_count += 1
	return bomb_count
for _ in range(int(input())):
	data = []
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		data.append((a, b))
	print(calc(data))


import math

def solve():
	n = int(input())
	arr = list()
	for _ in range(n):
		(first, second) = input().split(' ')
		arr.append([int(first), int(second)])
	arr = sorted(arr, key=lambda x: x[1])
	max_t = -math.inf
	cnt = 0
	for idx in range(n):
		if arr[idx][0] > max_t:
			max_t = arr[idx][1]
			cnt += 1
	print(cnt)

def main():
	t = int(input())
	while t:
		solve()
		t -= 1
main()


def printMinBombs(intervals, n):
	total = n
	(ps, pe) = (-1, -1)
	for interval in intervals:
		if pe == -1:
			(ps, pe) = interval
		elif interval[0] <= pe:
			total -= 1
			if interval[1] <= pe:
				pe = interval[1]
		else:
			(ps, pe) = interval
	return total
T = int(input())
for t in range(T):
	intervals = []
	n = int(input())
	for i in range(n):
		(st, en) = [int(j) for j in input().split()]
		intervals.append([st, en])
	intervals.sort()
	print(printMinBombs(intervals, n))


t = int(input())
for i in range(t):
	x = 0
	y = 3000
	z = 1
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	l.sort()
	for i in l:
		if i[0] > y:
			z += 1
			(x, y) = i
		else:
			x = i[0]
			y = min(y, i[1])
	print(z)


for i in range(int(input())):
	a = []
	for j in range(int(input())):
		a.append(input().split())
		a[-1][0] = int(a[-1][0])
		a[-1][1] = int(a[-1][1])
	a.sort()
	stack = []
	numb = 1
	queue = []
	minv = a[0][1]
	k = 0
	for i in range(1, len(a)):
		if a[i][0] > minv:
			numb += 1
			k = i
			minv = a[i][1]
			continue
		if minv > a[i][1]:
			minv = a[i][1]
	print(numb)


T = int(input())
arr = [-1] * 2003
for i in range(T):
	arr = [-1] * 2003
	lst = 0
	fst = 0
	N = int(input())
	for j in range(N):
		(x, y) = map(int, input().split())
		arr[y] = max(arr[y], x)
		lst = max(lst, y)
		fst = min(fst, y)
	mx = -1
	ans = 0
	for i in range(fst, lst + 1):
		if mx < arr[i]:
			mx = i
			ans += 1
	print(ans)


t = int(input())
while t:
	n = int(input())
	kingdoms = []
	for i in range(n):
		kingdoms.append(list(map(int, input().split())))
	kingdoms.sort(key=lambda x: x[1])
	curr = 0
	nex = 1
	bombs = 0
	while curr < n:
		while kingdoms[nex][0] <= kingdoms[curr][1]:
			nex += 1
			if nex == n:
				break
		bombs += 1
		if nex == n:
			break
		curr = nex
		nex += 1
		if nex == n:
			bombs += 1
			break
	print(bombs)
	t -= 1


from math import ceil, sqrt, log, gcd
from collections import deque, defaultdict as dd
from os import path
import sys
t = int(input())
for f in range(t):
	n = int(input())
	a = []
	x = 0
	y = 10000000
	count = 1
	for i in range(n):
		a.append(list(map(int, input().split())))
	a.sort()
	for i in range(n):
		if a[i][0] > y:
			count += 1
			x = a[i][0]
			y = a[i][1]
		else:
			x = a[i][0]
			y = min(a[i][1], y)
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append([a, b])
	l.sort()
	s = l[0][0]
	e = l[0][1]
	b = 0
	for i in range(1, n):
		if l[i][0] <= e:
			s = l[i][0]
			if l[i][1] <= e:
				e = l[i][1]
		else:
			b += 1
			s = l[i][0]
			e = l[i][1]
	print(b + 1)


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for j in range(n):
		l = list(map(int, input().split()))
		a.append(l)
	a.sort()
	b = 0
	c = 0
	while c < n:
		b += 1
		x = a[c][0]
		y = a[c][1]
		j = c + 1
		while j < n:
			if y >= a[j][0]:
				x = a[j][0]
				if a[j][1] < y:
					y = a[j][1]
				j += 1
			else:
				break
		c = j
	print(b)


def main():
	for _ in range(int(input())):
		kingdoms = sorted([[int(a) for a in input().split(' ')] for _ in range(int(input()))])
		i = kingdoms[0][0]
		j = kingdoms[0][-1]
		bombs = 1
		for a in kingdoms[1:]:
			if a[0] > j:
				i = a[0]
				j = a[1]
				bombs += 1
			else:
				j = a[1] if a[1] < j else j
		print(bombs)
main()


t = int(input())
for tt in range(t):
	n = int(input())
	dim = []
	for nn in range(n):
		(s, e) = map(int, input().split())
		dim.append((e, s))
	dim.sort()
	ans = 1
	(fi, se) = dim[0]
	for (e, s) in dim:
		if s <= fi:
			ans = ans
		else:
			fi = e
			ans = ans + 1
	print(ans)


def cnt_bomb(interv):
	interv = sorted(interv)
	cnt = 0
	last = None
	for (st, end) in interv:
		if last is None:
			last = (st, end)
		elif st > last[1]:
			cnt += 1
			last = (st, end)
		elif end < last[1]:
			last = (st, end)
		else:
			last = (st, last[1])
	return cnt + 1
T = int(input())
for t in range(T):
	n = int(input())
	interv = []
	for i in range(n):
		interv.append([int(x) for x in input().split()])
	print(cnt_bomb(interv))