We all know that Share market is place where drastic change occurs within moments. So we have one Stockholder, Isabella, who wants to maximize her profit by selling her shares. She has $N$ shares of a Doofenshmirtz Corporation which is represented by $N$ different lines where each line contains two space separated integers $a_i$ , $b_i$ corresponding to initial and final values of the share prize. Isabella can sell any number of shares. But, she will sell those shares only if the following condition is satisfied - 
- for any pair $(i,j)$ of shares that she choses to sell, $a_i \leq a_j$  and $b_i < b_j$ must be satisfied. 
You need to tell Isabella the maximum number of Shares she can sell.

-----Input:-----
- First line will contain $T$, number of test cases. 
- Each test case has the following format:
- First line of each test case contain single integer $N$, the number of shares of Isabella.  
- Next $N$ lines of each test case contain two space separated integers $a_i$, $b_i$ (initial and final value of share prize respectively) for each $1 \leq i \leq N$.

-----Output:-----
For each test case output a single integer: the maximum number of shares that can be sold by Isabella.

-----Constraints-----
- $1 \leq T \leq 5$
- $1 \leq N \leq 10^5$
- $1 \leq a_i , b_i \leq 10^9 , for  each $1$ \leq $i$ \leq $N 

-----Sample Input:-----
$1$
$4$ 
$1$ $2$
$4$ $3$
$3$ $5$ 
$2$ $4$ 

-----Sample Output:-----
$3$   

-----Explanation:-----
Here, Isabella decided to sell share 1, share 3 and share 4 as any two pair of 
chosen share hold the given condition.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def CeilIndex(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LongestIncreasingSubsequenceLength(A, size):
	tailTable = [0 for i in range(size + 1)]
	len = 0
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[len - 1]:
			tailTable[len] = A[i]
			len += 1
		else:
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]
	return len
t = int(input())
for _ in range(t):
	n = int(input())
	a = []
	for i in range(n):
		a.append(list(map(int, input().split())))
	a.sort()
	b = [0] * n
	for i in range(n):
		b[i] = a[i][1]
	print(LongestIncreasingSubsequenceLength(b, n))


def CeilIndex(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LongestIncreasingSubsequenceLength(A, size):
	tailTable = [0 for i in range(size + 1)]
	len = 0
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[len - 1]:
			tailTable[len] = A[i]
			len += 1
		else:
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]
	return len
for _ in range(int(input())):
	t = int(input())
	l = []
	for _ in range(t):
		(x, y) = map(int, input().split())
		l.append([x, y])
	l.sort()
	kk = []
	for (i, j) in l:
		kk.append(j)
	print(LongestIncreasingSubsequenceLength(kk, t))


def CeilIndex(A, l, r, key):
	while r - l > 1:
		m = l + (r - l) // 2
		if A[m] >= key:
			r = m
		else:
			l = m
	return r

def LongestIncreasingSubsequenceLength(A, size):
	tailTable = [0 for i in range(size + 1)]
	len = 0
	tailTable[0] = A[0]
	len = 1
	for i in range(1, size):
		if A[i] < tailTable[0]:
			tailTable[0] = A[i]
		elif A[i] > tailTable[len - 1]:
			tailTable[len] = A[i]
			len += 1
		else:
			tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i]
	return len
T = int(input())
while T:
	N = int(input())
	ls = []
	for i in range(N):
		(a, b) = map(int, input().split())
		ls.append([a, b])
	ls.sort()
	temp = [ls[i][1] for i in range(N)]
	print(LongestIncreasingSubsequenceLength(temp, N))
	T -= 1