Our chef has recently opened a new restaurant with a unique style. The restaurant is divided into K compartments (numbered from 1 to K) and each compartment can be occupied by at most one customer. 
Each customer that visits the restaurant has a strongly preferred compartment p (1 ≤ p ≤ K), and if that compartment is already occupied, then the customer simply leaves. Now obviously, the chef wants to maximize the total number of customers that dine at his restaurant and so he allows (or disallows) certain customers so as to achieve this task. You are to help him with this. 
Given a list of N customers with their arrival time, departure time and the preferred compartment, you need to calculate the maximum number of customers that can dine at the restaurant. 

-----Input-----
The first line contains an integer T denoting the number of test cases. Each of the next T lines contains two integers N and  K , the number of customers that plan to visit the chef's restaurant and the number of compartments the restaurant is divided into respectively. Each of the next N lines contains three integers si, fi and pi , the arrival time, departure time and the strongly preferred compartment of the ith customer respectively.  

Note that the ith customer wants to occupy the pith compartment from [si, fi)  i.e the ith customer leaves just before   fi  so that another customer can occupy that compartment from   fi  onwards.

-----Output-----
For every test case, print in a single line the maximum number of customers that dine at the restaurant.

-----Constraints-----
-  1 ≤  T ≤   30 
-  0  ≤ N  ≤  105 
-  1  ≤  K  ≤  109 
-  0  ≤  si < fi ≤   109 
-  1  ≤  pi  ≤  K  

-----Example-----
Input:
2
3 3
1 3 1
4 6 2
7 10 3
4 2
10 100 1
100 200 2
150 500 2
200 300 2

Output:
3
3

-----Explanation-----
Example case 1.

All three customers want different compartments and hence all 3 can be accommodated.

Example case 2.

If we serve the 1st, 2nd and 4th customers, then we can get a maximum of 3.

Difficulty: interview

Starter code:

Solutions:
try:
 for _ in range(int(input())):
  N, K = map(int, input().split())
  cell = []
  count = 0
  l = []
  for __ in range(N):
   inserted = list(map(int, input().split()))
   cell.append(inserted)



  




  cell.sort(key=lambda x: x[1])
  time = {}

  for number in cell:
   if number[2] not in time:
    time[number[2]] = number[1]

    count += 1
   elif number[0] >= time[number[2]]:
    time[number[2]] = number[1]
    count += 1





  print(count)


except:
 pass

from sys import stdin
input = stdin.readline
for i in range(int(input())):
 n,k = list(map(int, input().split()))
 l = []
 c = 0
 for g in range(n):
  adc = list(map(int, input().split()))
  l.append(adc)
 l.sort(key=lambda x: x[1])
 l.sort(key=lambda x: x[2])
 #for i in range(1,len(l)):
 i = 0
 j = 0
 while i<n:
  if i!=0:
   if l[i][2]!=l[i-1][2]:
    c+=1
    j = i
   else:
    if (l[i][0])>=(l[j][1]):
     c+=1
     j = i
  else:
   c+=1
  i+=1
 print(c)


# cook your dish here
from sys import stdin
input = stdin.readline
for i in range(int(input())):
 n,k = list(map(int, input().split()))
 l = []
 c = 0
 for g in range(n):
  adc = list(map(int, input().split()))
  l.append(adc)
 l.sort(key=lambda x: x[1])
 l.sort(key=lambda x: x[2])
 #for i in range(1,len(l)):
 i = 0
 j = 0
 while i<n:
  if i!=0:
   if l[i][2]!=l[i-1][2]:
    c+=1
    j = i
   else:
    if (l[i][0])>=(l[j][1]):
     c+=1
     j = i
  else:
   c+=1
  i+=1
 print(c)


# cook your dish here
def Max_cust(T):
 for i in range(T):
  count = 0
  cus_prefer = {}
  n,k = map(int,input().split())
  for j in range(n):
   s,f,p=map(int, input().split())
   if p not in cus_prefer:
    cus_prefer[p] = [(s,f)]
   else :
    cus_prefer[p].append((s,f))
  for v in cus_prefer.values():
   v.sort(key = lambda x:x[1])
   previous = (0,0)
   for item in v:
    if item[0] >= previous[1]:
     previous = item
     count += 1
  print(count)

t = int(input())
Max_cust(t)

from sys import stdin
input = stdin.readline

t=int(input())
for i in range(t):
 n,k=map(int,input().split())
 
 arr=[]
 for i in range(n):
  s,f,p=map(int,input().split())
  arr.append((s,f,p))
 
 arr.sort(key=lambda x:x[1])
 arr.sort(key=lambda x:x[2])

 i=0
 j=0
 cnt=0
 while i<n:
  if i!=0:
   if arr[i][2]!=arr[i-1][2]:
    cnt=cnt+1
    j=i
   else:
    if arr[i][0]>=arr[j][1]:
     cnt=cnt+1
     j=i
  else:
   cnt=cnt+1
  i=i+1 
 print(cnt) 

# cook your dish here
from collections import defaultdict

for _ in range(int(input())):
 n,k=list(map(int, input().split()))
 d=defaultdict(list)
 for i in range(n):
  s,f,p=list(map(int, input().split()))
  d[p].append([s, f])
  
 ans=0
 for i in d:
  if len(d[i])==1:
   ans+=1 
   
  else:
   d[i].sort(key=lambda x: x[1])
   t=0
   for j in range(len(d[i])):
    if d[i][j][0]>=t:
     ans+=1 
     t=d[i][j][1]
 print(ans)

t = int(input())

for _ in range(t):
 n, k = (int(i) for i in input().split())
 cust = [[int(i) for i in input().split()] for _ in range(n)]
 cust.sort(key=lambda x: x[1])
 
 compartments = {}
 ans = 0
 for x in cust:
  s, f, c = x
  if c in compartments:
   if compartments[c] <= s:
    compartments[c] = f
    ans += 1
  else:
   compartments[c] = f
   ans += 1
 
 print(ans)

# cook your dish here
from collections import defaultdict

for _ in range(int(input())):
 n,k=list(map(int, input().split()))
 d=defaultdict(list)
 for i in range(n):
  s,f,p=list(map(int, input().split()))
  d[p].append([s, f])
  
 ans=0
 for i in d:
  if len(d[i])==1:
   ans+=1 
   
  else:
   d[i].sort(key=lambda x: x[1])
   t=0
   for j in range(len(d[i])):
    if d[i][j][0]>=t:
     ans+=1 
     t=d[i][j][1]
 print(ans)

import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip("\r\n")

for _ in range(int(input())):
 n,k=list(map(int,input().split()))
 dic=defaultdict(lambda:[])
 for i in range(n):
  a,d,c=list(map(int,input().split()))
  dic[c].append((a,d))
 out=0
 for i in dic:
  dic[i].sort(key=lambda x:x[1])
  t=0
  j=0
  l=len(dic[i])
  while j<l:
   if t<=dic[i][j][0]:
    out+=1
    t=dic[i][j][1]
   j+=1
 print(out)


for _ in range(int(input())):
 n,k=list(map(int,input().split()))
 aux={}
 for i in range(n):
  s,f,p=list(map(int,input().split()))
  if p not in aux:
   aux[p]=[]
   aux[p].append([s,f])
  else:
   aux[p].append([s,f])
 tot=0
 for i in aux:
  # Sorting by finish time
  if len(aux[i])>1:
   aux[i].sort(key=lambda x:x[1])
   t_1=0
   for j in range(len(aux[i])):
    if aux[i][j][0]>=t_1:
     t_1=aux[i][j][1]
     tot+=1
  else:
   tot+=1
 print(tot)
  
  
  


t=int(input())
while(t>0):
 n,k=map(int,input().split())
 l=[]
 c=0
 for i in range(n):
  a,d,x=map(int,input().split())
  l.append((a,d,x))
 l.sort(key=lambda x:x[1])
 d={}
 for i in l:
  if(i[2] not in d):
   d[i[2]]=i[1]
   c+=1
  else:
   if(i[0]>=d[i[2]]):
    c+=1
    d[i[2]]=i[1]
 print(c)
 t-=1

# cook your dish here
from sys import stdin
for _ in range(int(input())):
 n,k = map(int,input().split())
 lst = []
 cmpmt={}
 cnt=0
 for i in range(n):
  si,fi,pi = map(int,stdin.readline().split())
  lst.append((fi,si,pi))
 lst = sorted(lst)
 for i in lst:
  if i[2] not in cmpmt:
   cmpmt[i[2]] = i[0]
   cnt +=1
  else:
   if cmpmt[i[2]] <= i[1]:
    cmpmt[i[2]]= i[0]
    cnt +=1
 print(cnt)

# cook your dish here
for _ in range(int(input())):
 ans = 0
 n,k = map(int,input().split())
 dic = {}
 for _ in range(n):
  s,f,p = map(int,input().split())
  if p not in dic:
   dic[p]= [(s,f)]
  else:
   dic[p].append((s,f))
 #print(dic)
 for key,val in dic.items():
  if len(dic[key])>1:
   x = 0
   for dekho in sorted(dic[key],key=lambda x:x[1]):
    if dekho[0]>=x:
     ans += 1 
     x = dekho[1]
    
  else:
   ans += 1 
 print(ans)

# cook your dish here
for _ in range(int(input())):
 ans = 0
 n,k = map(int,input().split())
 dic = {}
 for _ in range(n):
  s,f,p = map(int,input().split())
  if p not in dic:
   dic[p]= [(s,f)]
  else:
   dic[p].append((s,f))
 #print(dic)
 for key,val in dic.items():
  if len(dic[key])>1:
   x = 0
   for dekho in sorted(dic[key],key=lambda x:x[1]):
    if dekho[0]>=x:
     ans += 1 
     x = dekho[1]
    
  else:
   ans += 1 
 print(ans)

t = int(input())
while t > 0:
 n,k = map(int, input().split())
 temp = {}
 for i in range(n):
  s,f,p = map(int, input().split())
  if p in temp:
   temp[p].append([s,f])
  else:
   temp[p] = [[s,f]]

 cnt = 0
 for k in temp.keys():
  temp[k].sort(key = lambda x: x[1])
  prv = [0,0]
  for i in range(len(temp[k])):
   if temp[k][i][0] >= prv[1]:
    prv = temp[k][i]
    cnt += 1
 print(cnt)
 t -= 1

# cook your dish here
def fn_bonAppetit(test):
 for _ in range(test):
  n, k = map(int, input().split())
  cust_preference = {}
  for c in range(n):
   s, f, p = map(int, input().split())
   if p not in cust_preference:
    cust_preference[p] = [(s, f)]
   else:
    cust_preference[p].append((s, f))
  count = 0
  for v in cust_preference.values():
   v.sort(key = lambda x: x[1])
   previous = (0, 0)
   for item in v:
    if item[0] >= previous[1]:
     previous = item
     count += 1
  print(count)
  
test=int(input())
fn_bonAppetit(test)

def fn_bonAppetit(t):
 for test_case in range(t):
  # num of customers (n), num of compartments (k)
  n, k = map(int, input().split())
  cust_preference = {}
  # looping through each customer
  for c in range(n):
   # start, finish and preference
   s, f, p = map(int, input().split())
   if p not in cust_preference:
    cust_preference[p] = [(s, f)]
   else:
    cust_preference[p].append((s, f))
  
  count = 0
  for v in cust_preference.values():
   v.sort(key = lambda x: x[1]) # sort by finish time in-place
   previous = (0, 0)
   for item in v:
    if item[0] >= previous[1]:
     previous = item
     count += 1
  print(count)
  
t = int(input()) # total number of test cases
fn_bonAppetit(t)

# find disjoint intervals

from collections import defaultdict
for _ in range(int(input())):
 n, k = list(map(int, input().strip().split()))

 times = defaultdict(list)

 for i in range(n):
  start, finish, p = [int(x) for x in input().strip().split()]
  times[p].append((start, finish))

 ans = 0

 # print(times)
 for c in list(times.values()):
  c.sort(key = lambda x: x[1])
  finish_time = 0
  for st, ft in c:
   if st >= finish_time:
    ans += 1
    finish_time = ft 
 print(ans)


# cook your dish here
from sys import stdin
def cal(a):
 
 a.sort(key=lambda x:x[1])
 len1=len(a)
 c=1
 curr=a[0][1]
 for p in range(0,len1-1):
  if curr<=a[p+1][0]:
   c+=1
   curr=a[p+1][1]
 return c
 
 
 
t=int(input())
for i in range(t):
 n,k=list(map(int,stdin.readline().split()))
 list1=[]
 a=[]
 count=0
 for j in range(n):
  s,f,p=list(map(int,stdin.readline().split()))
  list1.append((s,f,p))
 list1.sort(key=lambda x:x[2])
 for j in range(0,n-1):
  if list1[j][2]==list1[j+1][2] and j!=n-2:
   a.append((list1[j][0],list1[j][1]))
  elif list1[j][2]==list1[j+1][2] and j==n-2:
   a.append((list1[j][0],list1[j][1]))
   a.append((list1[j+1][0],list1[j+1][1]))
   
   count+=cal(a)
   a=[]
  elif list1[j][2]!=list1[j+1][2] and j==n-2:
   a.append((list1[j][0],list1[j][1]))
   count+=cal(a)
   a=[]
   a.append((list1[j+1][0],list1[j+1][1]))
   count+=cal(a)
   a=[]
  else:
   a.append((list1[j][0],list1[j][1]))
   count+=cal(a)
   a=[]
 if n==1:
  print(count+1)
 else:
  print(count)


from sys import stdin,stdout
tc=int(stdin.readline())
for i in range(tc):
 n,k=list(map(int,stdin.readline().split()))
 dict1={}
 comp_to_iterate=[]
 for j in range(n):
  s,f,comp=list(map(int,stdin.readline().split()))
  if comp in dict1.keys():
   dict1[comp].append((s,f))
   if comp not in comp_to_iterate:
    comp_to_iterate.append(comp)
  else:
   dict1[comp]=[(s,f)]
 total=len(dict1.keys())-len(comp_to_iterate)
 for key in comp_to_iterate:
  value=dict1[key]
  value.sort(key=lambda x:x[1])
  el=value[0]
  l=1
  total+=1
  while l<len(value):
   if value[l][0]>=el[1]:
    total+=1
    el=value[l]
   l+=1
 print(total)

for i in range(int(input())):
 n,k=list(map(int,input().split()))
 dict1={}
 for j in range(n):
  s,e,p=list(map(int,input().split()))
  try:
   dict1[p].append((e,s))
  except:
   dict1[p]=[(e,s)]
   
 count=0
 for k in dict1:
  dict1[k].sort()
  start=-1
  for j in dict1[k]:
   if(j[1]>=start):
    start=j[0]
    count+=1
 print(count)


t=int(input())
for _ in range (t):
 n,k=map(int,input().split())
 d={}
 for i in range(n):
  s,f,p=map(int,input().split())
  try:
   d[p].append((f,s))
  except:
   d[p]=[(f,s)]
 ans=0
 for i in d:
  d[i].sort()
  start=-1
  for j in d[i]:
   if j[1]>=start:
    ans+=1
    start=j[0]
 print(ans)