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: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
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)


def solve(compartments):
	total = 0
	for compartment in compartments:
		people = compartments[compartment]
		people.sort(key=lambda x: x[1])
		prevFin = 0
		for person in people:
			(start, finish) = person
			if start >= prevFin:
				total += 1
				prevFin = finish
	return total

def main():
	T = int(input())
	for i in range(T):
		compartments = {}
		(N, K) = [int(num) for num in input().split()]
		for j in range(N):
			(s, f, p) = [int(num) for num in input().split()]
			if p not in compartments:
				compartments[p] = []
			compartments[p].append((s, f))
		print(solve(compartments))
main()


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	dic = {}
	for i in range(n):
		(s, f, p) = map(int, input().split())
		if p in dic:
			dic[p].append((f, s))
		else:
			dic[p] = [(f, s)]
	ans = 0
	for l in dic:
		dic[l].sort()
		temp = -1
		for m in dic[l]:
			if m[1] >= temp:
				ans += 1
				temp = m[0]
	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


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = 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
	for c in 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)


import sys
from collections import defaultdict

def ti():
	return tuple(map(int, input().split()))

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, k) = (int(i) for i in sys.stdin.readline().split())
	d = defaultdict(list)
	for i in range(n):
		(l, r, c) = (int(i) for i in sys.stdin.readline().split())
		d[c].append((r, l))
	for x in d:
		d[x].sort()
	ans = 0
	for x in d:
		t = 0
		for ele in d[x]:
			(r, l) = ele
			if l >= t:
				ans += 1
				t = r
	sys.stdout.write(str(ans) + '\n')


from collections import defaultdict

def solve():
	(n, k) = (int(i) for i in input().strip().split(' '))
	d = defaultdict(list)
	for i in range(n):
		(si, fi, pi) = (int(i) for i in input().strip().split(' '))
		d[pi].append((fi, si))
	ans = 0
	for i in d:
		d[i].sort()
	for key in d:
		c = 0
		for v in d[key]:
			(a, b) = v
			if b >= c:
				ans += 1
				c = a
	print(ans)
for _ in range(int(input())):
	solve()


import sys, math, numpy as np
from sys import stdin, stdout
mod = int(1000000000.0 + 7)
from collections import deque, defaultdict
from copy import deepcopy
from math import ceil, floor, inf, sqrt, factorial, gcd, log2
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
for _ in range(ii1()):
	(n, kebin) = iia()
	arr = []
	for i in range(n):
		a = iia()
		arr.append(a)
	arr.sort(key=lambda x: x[1])
	dic = {}
	count = 0
	for cus in arr:
		if cus[2] not in dic:
			dic[cus[2]] = cus[1]
			count += 1
		elif cus[0] >= dic[cus[2]]:
			dic[cus[2]] = cus[1]
			count += 1
	print(count)


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
			elif arr[i][0] >= arr[j][1]:
				cnt = cnt + 1
				j = i
		else:
			cnt = cnt + 1
		i = i + 1
	print(cnt)


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)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	m = {}
	for j in range(n):
		(arr, dep, k) = list(map(int, input().split()))
		if k in m:
			m[k].append([arr, dep])
		else:
			m[k] = [[arr, dep]]
	c = 0
	for temp in m.values():
		temp.sort(key=lambda x: x[1])
		ct = 1
		curr = 0
		ct1 = 1
		for temp1 in temp[1:]:
			if temp1[0] >= temp[curr][1]:
				curr = ct1
				ct += 1
			ct1 += 1
		c += ct
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	aux = {}
	for i in range(n):
		(s, f, p) = 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:
		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)


from collections import defaultdict
t = int(input())

def solve():
	(n, k) = map(int, input().split())
	d = defaultdict(list)
	for i in range(n):
		(l, r, c) = map(int, input().split())
		d[c].append((r, l))
	for x in d:
		d[x].sort()
	ans = 0
	for x in d:
		t = 0
		for i in d[x]:
			(r, l) = i
			if l >= t:
				ans += 1
				t = r
	print(ans)
while t:
	solve()
	t -= 1


from collections import defaultdict

def main():
	t = int(input().strip())
	for _ in range(t):
		(n, k) = list(map(int, input().strip().split()))
		customer_list = []
		for _ in range(n):
			customer_list.append(list(map(int, input().strip().split())))
		customer_list.sort(key=lambda x: x[1])
		count = 0
		comp = defaultdict(int)
		for cust in customer_list:
			if comp[cust[2]] <= cust[0]:
				comp[cust[2]] = cust[1]
				count += 1
		print(count)
main()


T = int(input())
for i in range(T):
	(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)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	data = []
	for i in range(n):
		(s, f, p) = map(int, input().split())
		data.append((s, f, p))
	data.sort(key=lambda x: x[0])
	compartments = dict()
	customers = 0
	for (s, f, p) in data:
		if p in compartments:
			if f < compartments[p][1]:
				compartments[p] = (s, f)
			elif s >= compartments[p][1]:
				compartments[p] = (s, f)
				customers += 1
		else:
			compartments[p] = (s, f)
			customers += 1
	print(customers)


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))
	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)


from collections import defaultdict

def solve():
	(n, k) = (int(i) for i in input().strip().split(' '))
	d = defaultdict(list)
	for i in range(n):
		(s, f, p) = (int(i) for i in input().strip().split(' '))
		d[p].append((f, s))
	for x in d:
		d[x].sort()
	ans = 0
	for x in d:
		t = 0
		for ele in d[x]:
			(f, s) = ele
			if s >= t:
				ans += 1
				t = f
	print(ans)
t = int(input())
for i in range(t):
	solve()


def fgfs(n, k, d):
	count = len(d)
	for num in d:
		(i, n) = (1, len(d[num]))
		times = d[num]
		initial = times[0]
		while i < n:
			if initial[1] <= times[i][0]:
				count += 1
				initial = times[i]
			i += 1
	return count
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	dic = {}
	for i in range(N):
		(s, f, p) = map(int, input().split())
		if p in dic.keys():
			dic[p].append([s, f])
		else:
			dic[p] = [[s, f]]
	for num in dic:
		dic[num] = sorted(dic[num], key=lambda x: x[1])
	print(fgfs(N, K, dic))


from collections import defaultdict
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	c = defaultdict(list)
	for _ in range(N):
		(s, f, p) = map(int, input().split())
		c[p].append((f, s))
	cust = 0
	for k in c:
		c[k].sort()
		t = 0
		for ele in c[k]:
			(r, l) = ele
			if l >= t:
				cust += 1
				t = r
	print(cust)


def main(n, k):
	customers = {}
	allowed = []
	for i in range(n):
		(s, f, p) = tuple(map(int, input().split()))
		customers.setdefault(p, []).append((s, f))
	for p in customers:
		interested = sorted(customers[p], key=lambda x: x[1])
		allowed.append(interested[0])
		for i in range(1, len(interested)):
			prev = allowed[-1]
			curr = interested[i]
			if curr[0] >= prev[1]:
				allowed.append(curr)
	return len(allowed)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(main(n, k))


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)


from sys import stdin
input = stdin.readline
for i in range(int(input())):
	(n, k) = 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])
	i = 0
	j = 0
	while i < n:
		if i != 0:
			if l[i][2] != l[i - 1][2]:
				c += 1
				j = i
			elif l[i][0] >= l[j][1]:
				c += 1
				j = i
		else:
			c += 1
		i += 1
	print(c)


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
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	m = {}
	f = {}
	c = 0
	for i in range(n):
		(s, e, c) = map(int, stdin.readline().split())
		v = [s, e, c]
		if c in m:
			m[c].append(v)
		else:
			m[c] = [v]
	c = 0
	for i in m:
		t = m[i]
		t = sorted(t, key=lambda x: x[1])
		for j in range(len(t)):
			if t[j][2] not in f:
				f[t[j][2]] = t[j][1]
				c += 1
			elif t[j][0] >= f[t[j][2]]:
				c += 1
				f[t[j][2]] = t[j][1]
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().strip().split())
	arr = {}
	for x in range(n):
		(s, f, p) = map(int, input().strip().split())
		if p not in arr:
			arr[p] = []
		arr[p].append((s, f))
	ans = 0
	for c in arr.values():
		c.sort(key=lambda x: x[1])
		f = 0
		for x in c:
			if x[0] >= f:
				ans += 1
				f = x[1]
	print(ans)


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())
		if p in d:
			d[p].append((f, s))
		else:
			d[p] = [(f, s)]
	count = 0
	for i in d:
		d[i].sort()
		start = -1
		for j in d[i]:
			if j[1] >= start:
				count += 1
				start = j[0]
	print(count)


def customer(n, k, cust):
	total = len(cust)
	for k in cust:
		m = len(cust[k])
		local = cust[k]
		prev = local[0]
		(i, n) = (1, m)
		while i < n:
			if prev[1] <= local[i][0]:
				total += 1
				prev = local[i]
			i += 1
	return total
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	cust = {}
	for _ in range(n):
		(a, d, p) = map(int, input().split())
		if p in cust.keys():
			cust[p].append([a, d])
		else:
			cust[p] = [[a, d]]
	for num in cust:
		cust[num] = sorted(cust[num], key=lambda x: x[1])
	out = customer(n, k, cust)
	print(out)


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)


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
		elif i[0] >= d[i[2]]:
			c += 1
			d[i[2]] = i[1]
	print(c)
	t -= 1


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) = [int(x) for x in input().split()]
	hmap = dict()
	for _ in range(n):
		(s, f, p) = [int(x) for x in input().split()]
		hmap.setdefault(p, []).append((s, f))
	ans = 0
	for (key, arr) in hmap.items():
		ans = ans + 1
		arr.sort(key=lambda x: x[1])
		curr = arr[0]
		for slot in arr:
			if slot[0] >= curr[1]:
				curr = slot
				ans = ans + 1
	print(ans)


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
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
		elif cmpmt[i[2]] <= i[1]:
			cmpmt[i[2]] = i[0]
			cnt += 1
	print(cnt)


from collections import defaultdict

def fun():
	(n, k) = (int(i) for i in input().strip().split(' '))
	d = defaultdict(list)
	for i in range(n):
		(l, r, c) = (int(i) for i in input().strip().split())
		d[c].append((r, l))
	for y in d:
		d[y].sort()
	ans = 0
	for y in d:
		t = 0
		for e in d[y]:
			(r, l) = e
			if l >= t:
				ans += 1
				t = r
	print(ans)
p = int(input())
for i in range(p):
	fun()


def find_max(schedule):
	schedule.sort(key=lambda k: k[1])
	result = 0
	free_at = -1
	for (s, f) in schedule:
		if s >= free_at:
			free_at = f
			result += 1
	return result

def solve(customers, K):
	schedules = {}
	result = 0
	for (s, f, p) in customers:
		if p not in schedules:
			schedules[p] = []
		schedules[p].append([s, f])
	for schedule in schedules.values():
		result += find_max(schedule)
	return result

def main():
	for _ in range(int(input())):
		(N, K) = map(int, input().split())
		customers = [[int(val) for val in input().split()] for _ in range(N)]
		print(solve(customers, K))
main()


import sys
from collections import defaultdict
t = int(sys.stdin.readline())
for i in range(t):
	(n, k) = (int(i) for i in sys.stdin.readline().split())
	d = defaultdict(list)
	for i in range(n):
		(l, r, c) = (int(i) for i in sys.stdin.readline().split())
		d[c].append((r, l))
	for x in d:
		d[x].sort()
	ans = 0
	for x in d:
		t = 0
		for ele in d[x]:
			(r, l) = ele
			if l >= t:
				ans += 1
				t = r
	sys.stdout.write(str(ans) + '\n')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mapi = {}
	for _ in range(n):
		(arr, dep, comp) = map(int, input().split())
		if comp in mapi:
			mapi[comp].append([dep, arr])
		else:
			mapi[comp] = [[dep, arr]]
	count = 0
	for comp in mapi.values():
		comp.sort(key=lambda x: x[0])
		prev = 0
		for curr in comp:
			if curr[1] >= prev:
				prev = curr[0]
				count += 1
	print(count)


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)


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


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


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	customers = {}
	for customer in range(n):
		temp = [int(x) for x in input().split()]
		if temp[2] in customers:
			customers[temp[2]].append(temp)
		else:
			customers[temp[2]] = [temp]
	happy_customers = 0
	for (comp, booth) in customers.items():
		booth.sort(key=lambda x: x[1], reverse=False)
		if len(booth) == 1:
			happy_customers += 1
			continue
		current_end = booth[0][1]
		happy_customers += 1
		for cust in booth:
			if cust[0] >= current_end:
				happy_customers += 1
				current_end = cust[1]
	print(happy_customers)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list()
	d = {}
	for i in range(n):
		(s, f, p) = list(map(int, input().split()))
		if p in d:
			d[p].append([s, f, p])
		else:
			d[p] = [[s, f, p]]
	count = 0
	for val in d.values():
		freeat = 0
		y = sorted(val, key=lambda x: x[1])
		for i in y:
			if freeat <= i[0]:
				freeat = i[1]
				count += 1
	print(count)


tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	mp = {}
	for cust in range(n):
		(s, f, p) = list(map(int, input().split()))
		if p in mp:
			mp[p].append([s, f])
		else:
			mp[p] = [[s, f]]
	ans = 0
	for lst in mp.values():
		lst.sort(key=lambda y: y[1])
		cnt = 1
		prev = 0
		i = 1
		for val in lst[1:]:
			if val[0] >= lst[prev][1]:
				prev = i
				cnt += 1
			i += 1
		ans += cnt
	print(ans)


try:
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		table = {}
		for _ in range(n):
			(start, end, pref) = map(int, input().split())
			if pref in table.keys():
				table[pref].add((end, start))
			else:
				table[pref] = set()
				table[pref].add((end, start))
		cnt = 0
		for key in table.keys():
			length = len(table[key])
			if length > 1:
				val = sorted(table[key])
				last_dept = 0
				for i in range(length):
					if val[i][1] >= last_dept:
						cnt += 1
						last_dept = val[i][0]
			else:
				cnt += 1
		print(cnt)
except:
	pass


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)


t = int(input())
for _ in range(t):
	arr = {}
	(n, k) = map(int, input().split())
	for i in range(n):
		(at, dt, sp) = map(int, input().split())
		if sp not in arr:
			arr[sp] = []
		arr[sp].append((at, dt))
	count = 0
	for val in arr.values():
		val.sort(key=lambda x: x[1])
		f = 0
		for x in val:
			if x[0] >= f:
				count = count + 1
				f = x[1]
	print(count)


t = int(input())
for testcase in range(t):
	(n, k) = map(int, input().split())
	rest = {}
	for cust in range(n):
		(s, f, p) = list(map(int, input().split()))
		if p in rest:
			rest[p].append([f, s])
		else:
			rest[p] = [[f, s]]
	count = 0
	for comp in rest.values():
		comp.sort(key=lambda x: x[0])
		last = 0
		for cust in comp:
			if cust[1] >= last:
				last = cust[0]
				count += 1
	print(count)


testcase = int(input())
for index in range(testcase):
	(customerNum, seat) = map(int, input().split())
	customers = {}
	for cust in range(customerNum):
		(custArrive, custDepart, custFavourite) = map(int, input().split())
		if custFavourite not in customers:
			customers[custFavourite] = [(custArrive, custDepart)]
		else:
			customers[custFavourite].append((custArrive, custDepart))
	count = 0
	for values in customers.values():
		values.sort(key=lambda x: x[1])
		previous = (0, 0)
		for item in values:
			if item[0] >= previous[1]:
				previous = item
				count += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	data = []
	tab = dict()
	for _ in range(n):
		(s, f, p) = map(int, input().split())
		data.append((s, f, p))
	data.sort(key=lambda x: x[0])
	coustomer = 0
	for (s, f, p) in data:
		if p in tab:
			if f <= tab[p][1]:
				tab[p] = (s, f)
			elif s >= tab[p][1]:
				tab[p] = (s, f)
				coustomer += 1
		else:
			tab[p] = (s, f)
			coustomer += 1
	print(coustomer)


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	dine_area = defaultdict(list)
	for customer in range(n):
		(s, e, pref) = map(int, input().split())
		dine_area[pref].append((s, e))

	def process(dine):
		interval = dine_area[dine]
		interval.sort(key=lambda x: x[1])
		customers = 1
		prev_end = interval[0][1]
		for (s, e) in interval[1:]:
			if s >= prev_end:
				prev_end = e
				customers += 1
		return customers
	total_customers = 0
	for dine in dine_area:
		total_customers += process(dine)
	print(total_customers)


t = int(input())
for p in range(t):
	(n, k) = map(int, input().split())
	l = {}
	for i in range(n):
		(a, b, c) = map(int, input().split())
		if c not in l:
			l[c] = [(a, b)]
		else:
			l[c].append((a, b))
	co = 0
	for i in l.values():
		i.sort(key=lambda x: x[1])
		pre = (0, 0)
		for j in i:
			if j[0] >= pre[1]:
				co = co + 1
				pre = j
	print(co, '\n')


T = int(input())
for z in range(T):
	(N, K) = map(int, input().split())
	lst = []
	for i in range(N):
		lst.append(tuple(map(int, input().split())))
	lst.sort(key=lambda x: x[0])
	res = 0
	dct = {}
	for (start, end, p) in lst:
		if p in dct.keys():
			if end <= dct[p][1]:
				dct[p] = [start, end]
			elif start >= dct[p][1]:
				dct[p] = [start, end]
				res += 1
		else:
			dct[p] = [start, end]
			res += 1
	print(res)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	customerslist = {}
	for j in range(n):
		(s, f, p) = map(int, input().split())
		if p in customerslist:
			customerslist[p].append([f, s])
		else:
			customerslist[p] = [[f, s]]
	count = 0
	for comp in customerslist.values():
		comp.sort()
		last = 0
		for cust in comp:
			if cust[1] >= last:
				last = cust[0]
				count += 1
	print(count)


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)