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.

Difficulty: interview

Starter code:

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): 
  
    # Add boundary case, 
    # when array size is one 
   
    tailTable = [0 for i in range(size + 1)] 
    len = 0 # always points empty slot 
   
    tailTable[0] = A[0] 
    len = 1
    for i in range(1, size): 
      
        if (A[i] < tailTable[0]): 
  
            # new smallest value 
            tailTable[0] = A[i] 
   
        elif (A[i] > tailTable[len-1]): 
  
            # A[i] wants to extend 
            # largest subsequence 
            tailTable[len] = A[i] 
            len+= 1
   
        else: 
            # A[i] wants to be current 
            # end candidate of an existing 
            # subsequence. It will replace 
            # ceil value in tailTable 
            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)) 


# cook your dish here
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): 

	# Add boundary case, 
	# when array size is one 

	tailTable = [0 for i in range(size + 1)] 
	len = 0 # always points empty slot 

	tailTable[0] = A[0] 
	len = 1
	for i in range(1, size): 
	
		if (A[i] < tailTable[0]): 

			# new smallest value 
			tailTable[0] = A[i] 

		elif (A[i] > tailTable[len-1]): 

			# A[i] wants to extend 
			# largest subsequence 
			tailTable[len] = A[i] 
			len+= 1

		else: 
			# A[i] wants to be current 
			# end candidate of an existing 
			# subsequence. It will replace 
			# ceil value in tailTable 
			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()
    # print(l)
    kk = []
    for (i,j) in l:
        kk.append(j)
    print(LongestIncreasingSubsequenceLength(kk, t))    

# Python program to find 
# length of longest 
# increasing subsequence 
# in O(n Log n) time 

# Binary search (note 
# boundaries in the caller) 
# A[] is ceilIndex 
# in the caller 
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): 

	# Add boundary case, 
	# when array size is one 

	tailTable = [0 for i in range(size + 1)] 
	len = 0 # always points empty slot 

	tailTable[0] = A[0] 
	len = 1
	for i in range(1, size): 
	
		if (A[i] < tailTable[0]): 

			# new smallest value 
			tailTable[0] = A[i] 

		elif (A[i] > tailTable[len-1]): 

			# A[i] wants to extend 
			# largest subsequence 
			tailTable[len] = A[i] 
			len+= 1

		else: 
			# A[i] wants to be current 
			# end candidate of an existing 
			# subsequence. It will replace 
			# ceil value in tailTable 
			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