Polycarp is very fond of playing the game Minesweeper. Recently he found a similar game and there are such rules.

There are mines on the field, for each the coordinates of its location are known ($x_i, y_i$). Each mine has a lifetime in seconds, after which it will explode. After the explosion, the mine also detonates all mines vertically and horizontally at a distance of $k$ (two perpendicular lines). As a result, we get an explosion on the field in the form of a "plus" symbol ('+'). Thus, one explosion can cause new explosions, and so on.

Also, Polycarp can detonate anyone mine every second, starting from zero seconds. After that, a chain reaction of explosions also takes place. Mines explode instantly and also instantly detonate other mines according to the rules described above.

Polycarp wants to set a new record and asks you to help him calculate in what minimum number of seconds all mines can be detonated.


-----Input-----

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

An empty line is written in front of each test suite.

Next comes a line that contains integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k \le 10^9$) — the number of mines and the distance that hit by mines during the explosion, respectively.

Then $n$ lines follow, the $i$-th of which describes the $x$ and $y$ coordinates of the $i$-th mine and the time until its explosion ($-10^9 \le x, y \le 10^9$, $0 \le timer \le 10^9$). It is guaranteed that all mines have different coordinates.

It is guaranteed that the sum of the values $n$ over all test cases in the test does not exceed $2 \cdot 10^5$.


-----Output-----

Print $t$ lines, each of the lines must contain the answer to the corresponding set of input data  — the minimum number of seconds it takes to explode all the mines.


-----Examples-----

Input
3

5 0
0 0 1
0 1 4
1 0 2
1 1 3
2 2 9

5 2
0 0 1
0 1 4
1 0 2
1 1 3
2 2 9

6 1
1 -1 3
0 -1 9
0 1 7
-1 0 1
-1 1 9
-1 -1 7
Output
2
1
0


-----Note-----

Picture from examples

First example:

$0$ second: we explode a mine at the cell $(2, 2)$, it does not detonate any other mine since $k=0$.

$1$ second: we explode the mine at the cell $(0, 1)$, and the mine at the cell $(0, 0)$ explodes itself.

$2$ second: we explode the mine at the cell $(1, 1)$, and the mine at the cell $(1, 0)$ explodes itself.

Second example:

$0$ second: we explode a mine at the cell $(2, 2)$ we get:

$1$ second: the mine at coordinate $(0, 0)$ explodes and since $k=2$ the explosion detonates mines at the cells $(0, 1)$ and $(1, 0)$, and their explosions detonate the mine at the cell $(1, 1)$ and there are no mines left on the field.

Difficulty: HARD
Tags: Spanning trees

Sorting

Graph traversal

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
class SDS:

	def __init__(self, n, mins):
		self.n = n
		self.parents = [i for i in range(n)]
		self.mins = mins

	def find(self, i):
		if self.parents[i] != i:
			self.parents[i] = self.find(self.parents[i])
		return self.parents[i]

	def union(self, i, j):
		(i, j) = (self.find(i), self.find(j))
		if i == j:
			return
		self.parents[j] = i
		self.mins[i] = min(self.mins[j], self.mins[i])

	def tolist(self):
		result = []
		for i in range(self.n):
			if i == self.parents[i]:
				result.append(self.mins[i])
		return (sorted(result), len(result))
result = []
for _ in range(int(input())):
	input()
	(n, k) = list(map(int, input().split()))
	mines = [list(map(int, input().split())) + [i] for i in range(n)]
	sds = SDS(n, list(map(lambda x: x[2], mines)))
	mines.sort(key=lambda x: (x[0], x[1]))
	(i, x, y) = (None, None, None)
	for mine in mines:
		if x == mine[0] and abs(mine[1] - y) <= k:
			sds.union(mine[3], i)
		(i, x, y) = (mine[3], mine[0], mine[1])
	mines.sort(key=lambda x: (x[1], x[0]))
	(i, x, y) = (None, None, None)
	for mine in mines:
		if y == mine[1] and abs(mine[0] - x) <= k:
			sds.union(mine[3], i)
		(i, x, y) = (mine[3], mine[0], mine[1])
	(mins, length) = sds.tolist()
	answer = length - 1
	for i in range(length):
		answer = min(answer, max(mins[i], length - i - 2))
	result.append(answer)
print('\n'.join(map(str, result)))


import sys
from collections import defaultdict
import typing

class DSU:

	def __init__(self, n: int=0) -> None:
		self._n = n
		self.parent_or_size = [-1] * n

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a < self._n
		assert 0 <= b < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a < self._n
		parent = self.parent_or_size[a]
		while parent >= 0:
			if self.parent_or_size[parent] < 0:
				return parent
			(self.parent_or_size[a], a, parent) = (self.parent_or_size[parent], self.parent_or_size[parent], self.parent_or_size[self.parent_or_size[parent]])
		return a

	def size(self, a: int) -> int:
		assert 0 <= a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self) -> typing.List[typing.List[int]]:
		leader_buf = [self.leader(i) for i in range(self._n)]
		result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		return list(filter(lambda r: r, result))

def input():
	return sys.stdin.readline().rstrip()
DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]
mod = 998244353
inf = 1 << 64

def slv():
	_ = input()
	(n, K) = map(int, input().split())
	mines = [tuple(map(int, input().split())) for i in range(n)]
	row_same = defaultdict(list)
	col_same = defaultdict(list)
	uf = DSU(n)
	for i in range(n):
		(row, col, time) = mines[i]
		row_same[row].append((col, i))
		col_same[col].append((row, i))
	for (k, v) in row_same.items():
		v.sort(key=lambda x: x[0])
		for i in range(len(v) - 1):
			if abs(v[i + 1][0] - v[i][0]) <= K:
				uf.merge(v[i + 1][1], v[i][1])
	for (k, v) in col_same.items():
		v.sort(key=lambda x: x[0])
		for i in range(len(v) - 1):
			if abs(v[i + 1][0] - v[i][0]) <= K:
				uf.merge(v[i + 1][1], v[i][1])
	exploding_time = []
	for g in uf.groups():
		min_time = inf
		for i in g:
			min_time = min(min_time, mines[i][-1])
		exploding_time.append(min_time)
	exploding_time.sort()

	def possible(X: int) -> bool:
		if X < 0:
			return False
		tmp = exploding_time.copy()
		for _ in range(X + 1):
			if not tmp:
				return True
			tmp.pop()
		if not tmp:
			return True
		return tmp[-1] <= X
	ng = -1
	ok = 10 ** 9 + 10
	while ok - ng > 1:
		med = (ng + ok) // 2
		if possible(med):
			ok = med
		else:
			ng = med
	print(ok)

def main():
	t = int(input())
	for i in range(t):
		slv()
	return 0
main()


from collections import defaultdict
import sys
input = sys.stdin.readline
get_int = lambda : int(input().rstrip())
get_arr = lambda : [int(w) for w in input().split()]
t = get_int()

class DSU:

	def __init__(self, size, arr):
		self.par = list(range(size))
		self.hs = [0] * size
		self.node2min = [arr[i][0] for i in range(size)]

	def find(self, i):
		if self.par[i] != i:
			self.par[i] = self.find(self.par[i])
		return self.par[i]

	def union(self, i, j):
		(pi, pj) = (self.find(i), self.find(j))
		if pi == pj:
			return
		if self.hs[pi] < self.hs[pj]:
			(pi, pj) = (pj, pi)
		self.par[pj] = pi
		self.node2min[pi] = min(self.node2min[pi], self.node2min[pj])
		self.hs[pi] += 1 if self.hs[pi] == self.hs[pj] else 0

def can(t, times):
	return times[len(times) - (t + 2)] <= t
for _ in range(t):
	input()
	(n, k) = get_arr()
	arr = []
	x2i = defaultdict(list)
	y2i = defaultdict(list)
	for i in range(n):
		(x, y, s) = get_arr()
		arr.append((s, x, y))
		x2i[x].append((y, i))
		y2i[y].append((x, i))
	dsu = DSU(n, arr)
	for x in x2i.keys():
		x2i[x].sort()
		for j in range(len(x2i[x]) - 1):
			(y1, i1) = x2i[x][j]
			(y2, i2) = x2i[x][j + 1]
			if y2 - y1 <= k:
				dsu.union(i1, i2)
	for y in y2i.keys():
		y2i[y].sort()
		for j in range(len(y2i[y]) - 1):
			(x1, i1) = y2i[y][j]
			(x2, i2) = y2i[y][j + 1]
			if x2 - x1 <= k:
				dsu.union(i1, i2)
	comps = {dsu.find(i) for i in range(n)}
	times = sorted([dsu.node2min[c] for c in comps])
	l = -1
	r = len(times) - 1
	while r - l >= 2:
		m = (l + r) // 2
		if can(m, times):
			r = m
		else:
			l = m
	print(r)


from collections import defaultdict
import sys
input = sys.stdin.buffer.readline

def find(pas, x):
	if pas[x] != x:
		pas[x] = find(pas, pas[x])
	return pas[x]

def union(pas, x, y):
	(fx, fy) = (find(pas, x), find(pas, y))
	if fx != fy:
		pas[fx] = fy
	return

def work(n, k, points, row, col, explosion_time):
	pas = list(range(n))
	for x in row:
		ps = []
		for i in row[x]:
			(px, py) = points[i]
			ps.append([py, px, i])
		ps.sort()
		for i in range(len(ps) - 1):
			dist = abs(ps[i][0] - ps[i + 1][0])
			if dist <= k:
				union(pas, ps[i][2], ps[i + 1][2])
	for y in col:
		ps = []
		for i in col[y]:
			(px, py) = points[i]
			ps.append([px, py, i])
		ps.sort()
		for i in range(len(ps) - 1):
			dist = abs(ps[i][0] - ps[i + 1][0])
			if dist <= k:
				union(pas, ps[i][2], ps[i + 1][2])
	mint = defaultdict(int)
	for i in range(n):
		fi = find(pas, i)
		time = explosion_time[i]
		if fi not in mint:
			mint[fi] = time
		else:
			mint[fi] = min(mint[fi], time)
	nodes = []
	for (fa, time) in mint.items():
		nodes.append([time, fa])
	nodes.sort()
	ans = 0
	nodes.pop()
	while nodes:
		(time, fa) = nodes.pop()
		if time > ans:
			ans += 1
	return ans

def main():
	test = int(input())
	for _ in range(test):
		_ = input()
		(n, k) = map(int, input().split())
		points = defaultdict(list)
		(row, col) = (defaultdict(list), defaultdict(list))
		explosion_time = defaultdict(int)
		for i in range(n):
			(x, y, t) = map(int, input().split())
			points[i] = [x, y]
			row[x].append(i)
			col[y].append(i)
			explosion_time[i] = t
		res = work(n, k, points, row, col, explosion_time)
		print(res)
	return
main()


import sys, os, io
from collections import defaultdict
input = sys.stdin.readline
PI = 3.141592653589793
INF = float('inf')
MOD = 1000000007

def bin32(num):
	return '{0:032b}'.format(num)

def add(x, y):
	return (x + y) % MOD

def sub(x, y):
	return (x - y + MOD) % MOD

def mul(x, y):
	return x * y % MOD

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def lcm(x, y):
	return x * y // gcd(x, y)

def power(x, y):
	res = 1
	x %= MOD
	while y != 0:
		if y & 1:
			res = mul(res, x)
		y >>= 1
		x = mul(x, x)
	return res

def mod_inv(n):
	return power(n, MOD - 2)

def prob(p, q):
	return mul(p, power(q, MOD - 2))

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

def li():
	return [int(i) for i in input().split()]

def ls():
	return [i for i in input().split()]

class DSU:
	maxi = 1
	node = -1

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		if self.maxi <= -self.c[self.find(u)]:
			self.maxi = max(self.maxi, -self.c[self.find(u)])
			self.node = self.find(u)
		return True

	def size(self, x):
		return -self.c[self.find(x)]
for t in range(ii()):
	t += 1
	s = input().strip()
	(n, k) = li()
	x = defaultdict(lambda : [])
	y = defaultdict(lambda : [])
	timer = [0 for i in range(n)]
	for i in range(n):
		a = li()
		x[a[0]].append([a[1], i])
		y[a[1]].append([a[0], i])
		timer[i] = a[2]
	dsu = DSU(n + 1)
	for xx in x:
		x[xx].sort()
		i = 0
		j = 1
		N = len(x[xx])
		while i < N:
			if i == j:
				j += 1
			while j < N and abs(x[xx][j][0] - x[xx][i][0]) <= k:
				dsu.union(x[xx][j][1], x[xx][i][1])
				j += 1
			i += 1
	for xx in y:
		y[xx].sort()
		i = 0
		j = 1
		N = len(y[xx])
		while i < N:
			if i == j:
				j += 1
			while j < N and abs(y[xx][j][0] - y[xx][i][0]) <= k:
				dsu.union(y[xx][j][1], y[xx][i][1])
				j += 1
			i += 1
	store = []
	g = [INF for i in range(n + 1)]
	for i in range(n):
		g[dsu.find(i)] = min(g[dsu.find(i)], timer[i])
	for i in g:
		if i != INF:
			store.append(i)
	store.sort()
	tm = -1
	while len(store) and store[-1] > tm:
		tm += 1
		store.pop()
	print(tm)


class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)
from collections import defaultdict

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		input()
		(n, k) = readIntArr()
		mines = []
		for __ in range(n):
			(x, y, time) = readIntArr()
			mines.append((x, y, time))
		uf = UnionFind(n)
		sameCols = defaultdict(lambda : [])
		sameRows = defaultdict(lambda : [])
		for (i, (x, y, time)) in enumerate(mines):
			sameCols[x].append((y, i))
			sameRows[y].append((x, i))
		for arr in sameCols.values():
			arr.sort()
			m = len(arr)
			for i in range(1, m):
				if arr[i][0] - arr[i - 1][0] <= k:
					uf.union(arr[i][1], arr[i - 1][1])
		for arr in sameRows.values():
			arr.sort()
			m = len(arr)
			for i in range(1, m):
				if arr[i][0] - arr[i - 1][0] <= k:
					uf.union(arr[i][1], arr[i - 1][1])
		inf = int(2000000000.0)
		minExplosionTime = [inf] * n
		for mine in range(n):
			z = minExplosionTime[uf.find(mine)]
			minExplosionTime[uf.find(mine)] = min(z, mines[mine][2])
		explosionTimes = []
		for time in minExplosionTime:
			if time != inf:
				explosionTimes.append(time)
		explosionTimes.sort()
		ans = inf
		backCnts = len(explosionTimes)
		for i in range(-1, len(explosionTimes)):
			if i == -1:
				et = 0
			else:
				et = explosionTimes[i]
			ans = min(ans, max(et, backCnts - 1))
			backCnts -= 1
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
	print('? {} {} {}'.format(a, b, c))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ansArr):
	print('! {}'.format(' '.join([str(x) for x in ansArr])))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
	main()


from sys import stdin
input = stdin.readline

class dsu:

	def __init__(self, n):
		self.p = [0] * (n + 1)
		self.rank = [0] * (n + 1)
		for i in range(1, n + 1):
			self.p[i] = i

	def find(self, node):
		if self.p[node] == node:
			return node
		self.p[node] = self.find(self.p[node])
		return self.p[node]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if self.rank[u] == self.rank[v]:
			self.p[v] = u
			self.rank[u] += 1
		elif self.rank[u] > self.rank[v]:
			self.p[v] = u
		else:
			self.p[u] = v

def solve(a, n):
	j = 0
	for i in range(n):
		while j < n and a[j][0] <= a[i][0] + k:
			(x, y) = (comp.find(a[i][1]), comp.find(a[j][1]))
			if x != y:
				time[x] = min(time[x], time[y])
				time[y] = min(time[y], time[x])
			comp.union(a[i][1], a[j][1])
			j += 1

def answer():
	for x in ax.keys():
		solve(ax[x], len(ax[x]))
	for y in ay.keys():
		solve(ay[y], len(ay[y]))
	allcomp = set()
	for i in range(1, n + 1):
		allcomp.add(comp.find(i))
	value = []
	for i in allcomp:
		value.append(time[i])
	value.sort(reverse=True)
	ans = -1
	for i in range(len(value)):
		if i > value[i]:
			break
		ans += 1
	return ans
for T in range(int(input())):
	input().strip()
	(n, k) = map(int, input().split())
	(ax, ay) = (dict(), dict())
	time = [0] * (n + 1)
	for i in range(n):
		(x, y, timeval) = map(int, input().split())
		ax[x] = ax.get(x, []) + [[y, i + 1, timeval]]
		ay[y] = ay.get(y, []) + [[x, i + 1, timeval]]
		time[i + 1] = timeval
	for x in ax.keys():
		ax[x].sort()
	for y in ay.keys():
		ay[y].sort()
	comp = dsu(n)
	print(answer())


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	a = []
	for i in range(n):
		(x, y, t) = map(int, input().split())
		a.append((i, x, y, t))
	ax = sorted(a, key=lambda x: (x[1], x[2]))
	ay = sorted(a, key=lambda x: (x[2], x[1]))
	e = {}
	for i in range(n):
		e[i] = []
	for i in range(n - 1):
		if ax[i][1] == ax[i + 1][1] and ax[i + 1][2] - ax[i][2] <= k:
			e[ax[i][0]].append(ax[i + 1][0])
			e[ax[i + 1][0]].append(ax[i][0])
		if ay[i][2] == ay[i + 1][2] and ay[i + 1][1] - ay[i][1] <= k:
			e[ay[i][0]].append(ay[i + 1][0])
			e[ay[i + 1][0]].append(ay[i][0])
	v = [False] * n
	b = []
	for i in range(n):
		if not v[i]:
			v[i] = True
			q = [i]
			d = 10000000000
			while len(q) > 0:
				p = q.pop()
				d = min(d, a[p][3])
				for x in e[p]:
					if not v[x]:
						v[x] = True
						q.append(x)
			b.append(d)
	b.sort(reverse=True)
	t = -1
	for i in range(len(b)):
		if b[i] <= t:
			break
		t += 1
	return t
t = int(input())
z = []
for i in range(t):
	input()
	z.append(str(solve()))
print('\n'.join(z))


import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
	I()
	(n, k) = I()
	rows = {}
	cols = {}
	mines = []
	for i in range(n):
		(x, y, t) = I()
		mines.append((x, y, t))
		if x in cols:
			cols[x].append((y, i, t))
		else:
			cols[x] = [(y, i, t)]
		if y in rows:
			rows[y].append((x, i, t))
		else:
			rows[y] = [(x, i, t)]
	rowind = [-1] * n
	colind = [-1] * n
	for x in cols:
		cols[x].sort()
		for i in range(len(cols[x])):
			colind[cols[x][i][1]] = i
	for y in rows:
		rows[y].sort()
		for j in range(len(rows[y])):
			rowind[rows[y][j][1]] = j
	comps = [-1] * n
	short = []
	num = 0
	for i in range(n):
		if comps[i] == -1:
			layer = [i]
			comps[i] = num
			sml = 1000000000
			while layer != []:
				newlayer = []
				for j in layer:
					(x, y, t) = mines[j]
					sml = min(t, sml)
					ind = rowind[j] - 1
					while ind >= 0 and comps[rows[y][ind][1]] == -1 and (rows[y][ind][0] >= x - k):
						a = rows[y][ind][1]
						newlayer.append(a)
						comps[a] = num
						ind -= 1
					ind = rowind[j] + 1
					while ind < len(rows[y]) and comps[rows[y][ind][1]] == -1 and (rows[y][ind][0] <= x + k):
						a = rows[y][ind][1]
						newlayer.append(a)
						comps[a] = num
						ind += 1
					ind = colind[j] - 1
					while ind >= 0 and comps[cols[x][ind][1]] == -1 and (cols[x][ind][0] >= y - k):
						a = cols[x][ind][1]
						newlayer.append(a)
						comps[a] = num
						ind -= 1
					ind = colind[j] + 1
					while ind < len(cols[x]) and comps[cols[x][ind][1]] == -1 and (cols[x][ind][0] <= y + k):
						a = cols[x][ind][1]
						newlayer.append(a)
						comps[a] = num
						ind += 1
				layer = newlayer
			num += 1
			short.append(sml)
	short.sort()
	l = len(short)
	need = l - 1
	for i in range(l):
		if short[i] < l - 1 - i:
			need -= 1
	print(need)


import collections
import io, os
import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, namedtuple
from heapq import heappush, heappop
from math import gcd, ceil, floor, factorial, sqrt
from itertools import combinations, permutations
input = sys.stdin.buffer.readline

def find(pas, x):
	if pas[x] != x:
		pas[x] = find(pas, pas[x])
	return pas[x]

def union(pas, x, y):
	(fx, fy) = (find(pas, x), find(pas, y))
	if fx != fy:
		pas[fx] = fy
	return

def work(n, k, points, explosion_time, row, col):
	pas = list(range(n))
	for x in row:
		ps = []
		for pid in row[x]:
			(px, py) = points[pid]
			ps.append([py, pid])
		ps.sort()
		for i in range(len(ps) - 1):
			dist = abs(ps[i][0] - ps[i + 1][0])
			if dist <= k:
				union(pas, ps[i][1], ps[i + 1][1])
	for y in col:
		ps = []
		for pid in col[y]:
			(px, py) = points[pid]
			ps.append([px, pid])
		ps.sort()
		for i in range(len(ps) - 1):
			dist = abs(ps[i][0] - ps[i + 1][0])
			if dist <= k:
				union(pas, ps[i][1], ps[i + 1][1])
	fas = defaultdict(list)
	mint = defaultdict(int)
	for i in range(n):
		fi = find(pas, i)
		fas[fi].append(i)
		if fi not in mint:
			mint[fi] = explosion_time[i]
		else:
			mint[fi] = min(mint[fi], explosion_time[i])
	fat = []
	for (key, v) in mint.items():
		fat.append([v, key])
	fat.sort()
	m = len(fat)
	ans = 0
	fat.pop()
	while fat:
		(t, node) = fat[-1]
		if t > ans:
			ans += 1
		fat.pop()
	return ans
	cnt = 0
	st = defaultdict(int)
	ans = 0
	mines = []
	time = defaultdict(list)
	for i in range(n):
		mines.append([explosion_time[i], i])
		time[explosion_time[i]].append(i)
	mines.sort(reverse=True)

def main():
	test = int(input())
	for idt in range(test):
		_ = input()
		(n, k) = map(int, input().split())
		points = defaultdict(list)
		explosion_time = defaultdict(list)
		(row, col) = (defaultdict(list), defaultdict(list))
		for i in range(n):
			(x, y, t) = map(int, input().split())
			points[i] = [x, y]
			explosion_time[i] = t
			row[x].append(i)
			col[y].append(i)
		ans = work(n, k, points, explosion_time, row, col)
		print(ans)
	return
main()


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
stinput = lambda : stdin.readline()[:-1]
ii = lambda : int(stinput())
mi = lambda : map(int, stdin.readline().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, stdin.readline().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, stdin.readline().split())
lis = lambda : list(mis())
from collections import defaultdict
import heapq
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0
from collections import defaultdict

class UnionFind:

	def __init__(self, n, time):
		self.time = time
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		mn = min(self.time[x], self.time[y])
		self.time[x] = mn
		self.time[y] = mn
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		group_members = defaultdict(list)
		for member in range(self.n):
			group_members[self.find(member)].append(member)
		return group_members

	def __str__(self):
		return '\n'.join((f'{r}: {m}' for (r, m) in self.all_group_members().items()))
t = ii()
for _ in range(t):
	stinput()
	(n, d) = mi()
	time = [0] * n
	X = defaultdict(list)
	Y = defaultdict(list)
	for i in range(n):
		(x, y, T) = mi()
		time[i] = T
		X[x].append((y, i))
		Y[y].append((x, i))
	uf = UnionFind(n, time)
	for x in X:
		s = sorted(X[x])
		m = len(s)
		for i in range(m - 1):
			if s[i + 1][0] - s[i][0] <= d:
				id1 = s[i + 1][1]
				id2 = s[i][1]
				uf.union(id1, id2)
	for y in Y:
		s = sorted(Y[y])
		m = len(s)
		for i in range(m - 1):
			if s[i + 1][0] - s[i][0] <= d:
				id1 = s[i + 1][1]
				id2 = s[i][1]
				uf.union(id1, id2)
	todo = []
	for i in uf.roots():
		todo.append(uf.time[i])
	todo.sort(reverse=True)
	ans = 0
	for i in range(1, len(todo)):
		if ans < todo[i]:
			ans += 1
	print(ans)


import collections

class DisjointSet:

	def __init__(self, init):
		self.d = {}
		for x in init:
			self.make_set(x)

	def make_set(self, x):
		if x in self.d:
			return
		self.d[x] = [x, 1]

	def find(self, x):
		if self.d[x][0] != x:
			self.d[x][0] = self.find(self.d[x][0])
			return self.d[x][0]
		return x

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.d[x][1] < self.d[y][1]:
			(x, y) = (y, x)
		self.d[y][0] = x
		self.d[x][1] += self.d[y][1]

	def __str__(self):
		return f'Disjoint set with elements {self.d}'

	def __repr__(self):
		return str(self)

def solve():
	input()
	(n, k) = list(map(int, input().split()))
	points = []
	for _ in range(n):
		points += [list(map(int, input().split()))]
	xs = collections.defaultdict(list)
	ys = collections.defaultdict(list)
	times = collections.defaultdict(int)
	for (i, (x, y, timer)) in enumerate(points):
		xs[x] += [(y, i)]
		ys[y] += [(x, i)]
		times[i] = timer
	DS = DisjointSet(range(n))
	for x in xs:
		xs[x].sort()
		for i in range(1, len(xs[x])):
			if xs[x][i][0] - xs[x][i - 1][0] > k:
				continue
			DS.union(xs[x][i][1], xs[x][i - 1][1])
	for y in ys:
		ys[y].sort()
		for i in range(1, len(ys[y])):
			if ys[y][i][0] - ys[y][i - 1][0] > k:
				continue
			DS.union(ys[y][i][1], ys[y][i - 1][1])
	comp_time = collections.defaultdict(lambda : 10000000000.0)
	for i in range(n):
		f = DS.find(i)
		comp_time[f] = min(comp_time[f], times[i])
	all_times = sorted(list(comp_time.values()))
	ans = max((min(all_times[i], len(all_times) - i - 1) for i in range(len(all_times))))
	print(ans)
for _ in range(int(input())):
	solve()


import sys
Z = sys.stdin.readline
Y = lambda : map(int, Z().split())
X = range
from collections import defaultdict as D

class U:

	def __init__(self, n):
		self.p = [*X(n)]

	def f(self, a):
		b = a
		while a != self.p[a]:
			a = self.p[a]
		while b != a:
			(self.p[b], b) = (a, self.p[b])
		return a
O = []
N = 10 ** 10
for _ in X(int(Z())):
	Z()
	(n, k) = Y()
	G = D(list)
	a = []
	u = U(n)
	b = []
	for i in X(n):
		(x, y, t) = Y()
		a.append(t)
		G[x].append((y, i))
		G[y + N].append((x, i))
	for x in G:
		g = G[x]
		L = len(g)
		g.sort()
		if L > 1:
			for i in X(1, L):
				v = u.f(g[i - 1][1])
				w = u.f(g[i][1])
				if v != w and g[i][0] - g[i - 1][0] <= k:
					u.p[w] = v
					a[v] = min(a[v], a[w])
					a[w] = N
	b = sorted((i for i in a if i < N))
	c = 0
	while c < len(b) - 1 and b[-2 - c] > c:
		c += 1
	print(c)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
	s = input()
	(n, k) = map(int, input().split())
	group = [i for i in range(n)]
	mintime = []
	dicx = {}
	dicy = {}
	for i in range(n):
		(x, y, time) = map(int, input().split())
		if x not in dicx:
			dicx[x] = []
		dicx[x].append([y, i])
		if y not in dicy:
			dicy[y] = []
		dicy[y].append([x, i])
		mintime.append(time)
	for key in dicx:
		dicx[key].sort()
	for key in dicy:
		dicy[key].sort()

	def unionfind(root):
		son = root
		while root != group[root]:
			root = group[root]
		while son != root:
			temp = group[son]
			group[son] = root
			son = group[temp]
		return root
	for key in dicx:
		arr = dicx[key]
		for i in range(len(arr) - 1):
			if arr[i + 1][0] - arr[i][0] > k:
				continue
			(root1, root2) = (arr[i][1], arr[i + 1][1])
			root1 = unionfind(root1)
			root2 = unionfind(root2)
			if root1 == root2:
				continue
			group[max(root1, root2)] = min(root1, root2)
	for key in dicy:
		arr = dicy[key]
		for i in range(len(arr) - 1):
			if arr[i + 1][0] - arr[i][0] > k:
				continue
			(root1, root2) = (arr[i][1], arr[i + 1][1])
			root1 = unionfind(root1)
			root2 = unionfind(root2)
			if root1 == root2:
				continue
			group[max(root1, root2)] = min(root1, root2)
	for i in range(n):
		group[i] = group[unionfind(i)]
		mintime[group[i]] = min(mintime[group[i]], mintime[i])
	grouptime = []
	for i in range(n):
		if i == group[i]:
			grouptime.append(mintime[i])
	grouptime.sort()
	ans = 0
	for i in range(len(grouptime)):
		ans = max(ans, min(grouptime[i], len(grouptime) - i - 1))
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


from collections import defaultdict
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
	v = []
	while not s == root[s]:
		v.append(s)
		s = root[s]
	for i in v:
		root[i] = s
	return s

def unite(s, t):
	(rs, rt) = (get_root(s), get_root(t))
	if not rs ^ rt:
		return
	if rank[s] == rank[t]:
		rank[rs] += 1
	if rank[s] >= rank[t]:
		root[rt] = rs
		size[rs] += size[rt]
	else:
		root[rs] = rt
		size[rt] += size[rs]
	return

def same(s, t):
	return True if get_root(s) == get_root(t) else False

def get_size(s):
	return size[get_root(s)]
t = int(input())
inf = pow(10, 9) + 1
ans = []
for _ in range(t):
	input()
	(n, k) = map(int, input().split())
	x = defaultdict(lambda : [])
	y = defaultdict(lambda : [])
	c = []
	for i in range(n):
		(x0, y0, c0) = map(int, input().split())
		x[x0].append((y0, i))
		y[y0].append((x0, i))
		c.append(c0)
	root = [i for i in range(n)]
	rank = [1 for _ in range(n)]
	size = [1 for _ in range(n)]
	for x0 in x.values():
		x0.sort()
		for i in range(len(x0) - 1):
			(u0, u) = x0[i]
			(v0, v) = x0[i + 1]
			if abs(u0 - v0) <= k:
				unite(u, v)
	for y0 in y.values():
		y0.sort()
		for i in range(len(y0) - 1):
			(u0, u) = y0[i]
			(v0, v) = y0[i + 1]
			if abs(u0 - v0) <= k:
				unite(u, v)
	s = [inf] * n
	for i in range(n):
		r = get_root(i)
		s[r] = min(s[r], c[i])
	s.sort()
	while s and s[-1] == inf:
		s.pop()
	c = 0
	ans0 = 0
	for i in range(len(s) - 1, -1, -1):
		ans0 = max(ans0, min(s[i], c))
		c += 1
	ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))


import sys, collections, math, bisect, heapq, random, functools, io, os, copy
input = sys.stdin.readline
out = sys.stdout.flush

def rep():
	a = list(map(int, input().split()))
	return a

def sep():
	a = list(input().split())
	return a

class UnionFind:

	def __init__(self, x) -> None:
		self.uf = [-1] * x

	def find(self, x):
		r = x
		while self.uf[x] >= 0:
			x = self.uf[x]
		while r != x:
			(self.uf[r], r) = (x, self.uf[r])
		return x

	def union(self, x, y):
		(ux, uy) = (self.find(x), self.find(y))
		if ux == uy:
			return
		if self.uf[ux] >= self.uf[uy]:
			self.uf[uy] += self.uf[ux]
			self.uf[ux] = uy
		else:
			self.uf[ux] += self.uf[uy]
			self.uf[uy] = ux
		return

	def __print__(self):
		return self.uf

def spfa(x, g, n):
	dis = [float('inf') for i in range(n)]
	dis[x] = 0
	state = [False for i in range(n)]
	state[x] = True
	queue = collections.deque()
	queue.append(x)
	while queue:
		cur = queue.popleft()
		state[cur] = False
		for next_ in g[cur]:
			if dis[next_] > dis[cur] + 1:
				dis[next_] = dis[cur] + 1
				if state[next_] == False:
					state[next_] = True
					queue.append(next_)
	return dis

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)

def solve():
	input()
	(n, k) = map(int, input().split())
	uf = UnionFind(n)
	time = [0 for i in range(n)]
	row = collections.defaultdict(list)
	column = collections.defaultdict(list)
	for i in range(n):
		(x, y, t) = map(int, input().split())
		row[x].append([y, i])
		column[y].append([x, i])
		time[i] = t
	for c in row:
		row[c].sort()
		(l, r) = (0, 1)
		N = len(row[c])
		while l < N:
			if l == r:
				r += 1
			while r < N and abs(row[c][l][0] - row[c][r][0]) <= k:
				uf.union(row[c][l][1], row[c][r][1])
				r += 1
			l += 1
	for c in column:
		column[c].sort()
		(l, r) = (0, 1)
		while l < len(column[c]):
			if l == r:
				r += 1
			while r < len(column[c]) and abs(column[c][l][0] - column[c][r][0]) <= k:
				uf.union(column[c][l][1], column[c][r][1])
				r += 1
			l += 1
	g = [float('inf') for i in range(n)]
	for i in range(n):
		g[uf.find(i)] = min(g[uf.find(i)], time[i])
	queue = []
	for c in g:
		if c != float('inf'):
			queue.append(c)
	queue.sort()
	cur = -1
	while queue and queue[-1] > cur:
		cur += 1
		queue.pop()
	print(cur)
for i in range(int(input())):
	solve()


import sys

def read_line():
	return sys.stdin.readline().strip()

def read_ints_line():
	return tuple([int(x) for x in read_line().split()])

def bfs(x, y, t, k, i_by_x, i_by_y, was, i):
	min_t = t[i]
	current_queue = [i]
	was[i] = True
	while len(current_queue) > 0:
		next_queue = []
		for i in current_queue:
			min_t = min(min_t, t[i])
			for next_i in i_by_x[x[i]]:
				if y[i] - k <= y[next_i] <= y[i] + k and (not was[next_i]):
					next_queue.append(next_i)
					was[next_i] = True
			for next_i in i_by_y[y[i]]:
				if x[i] - k <= x[next_i] <= x[i] + k and (not was[next_i]):
					next_queue.append(next_i)
					was[next_i] = True
		current_queue = next_queue
	return min_t
t = int(read_line())
for _ in range(t):
	read_line()
	(n, k) = read_ints_line()
	x = [0] * n
	y = [0] * n
	t = [0] * n
	for i in range(n):
		(x[i], y[i], t[i]) = read_ints_line()
	i_by_x = {}
	i_by_y = {}
	for i in range(n):
		if x[i] not in i_by_x:
			i_by_x[x[i]] = []
		if y[i] not in i_by_y:
			i_by_y[y[i]] = []
		i_by_x[x[i]].append(i)
		i_by_y[y[i]].append(i)
	was = [False] * n
	time_to_kill = []
	for i in range(n):
		if not was[i]:
			time_to_kill.append(bfs(x, y, t, k, i_by_x, i_by_y, was, i))
	time_to_kill.sort(reverse=True)
	for i in range(len(time_to_kill)):
		time_to_kill[i] = min(i, time_to_kill[i])
	print(f'{max(time_to_kill)}')


from sys import stdin, stdout

class DisjointSetUnion:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets
T = int(stdin.readline())
for _ in range(T):
	stdin.readline()
	(n, k) = [int(x) for x in stdin.readline().split()]
	mines = []
	mines_by_x = {}
	mines_by_y = {}
	timings = []
	for i in range(n):
		(x, y, t) = [int(z) for z in stdin.readline().split()]
		mines.append((x, y, t))
		timings.append(t)
		if x in mines_by_x:
			mines_by_x[x].append((y, t, i))
		else:
			mines_by_x[x] = [(y, t, i)]
		if y in mines_by_y:
			mines_by_y[y].append((x, t, i))
		else:
			mines_by_y[y] = [(x, t, i)]
	for x in mines_by_x:
		mines_by_x[x].sort()
	for y in mines_by_y:
		mines_by_y[y].sort()
	groups = DisjointSetUnion(n)
	for i in range(n):
		(x, y, t) = mines[i]
		x_line = mines_by_x[x]
		if len(x_line) > 1:
			lower = 0
			upper = len(x_line)
			while upper - lower > 1:
				candidate = (upper + lower) // 2
				if x_line[candidate][0] <= y:
					lower = candidate
				else:
					upper = candidate
			if lower > 0 and y - x_line[lower - 1][0] <= k:
				left_i = x_line[lower - 1][2]
				left_t = timings[groups.find(left_i)]
				self_t = timings[groups.find(i)]
				groups.union(i, left_i)
				timings[groups.find(i)] = min(self_t, left_t)
			if lower < len(x_line) - 1 and x_line[lower + 1][0] - y <= k:
				right_i = x_line[lower + 1][2]
				right_t = timings[groups.find(right_i)]
				self_t = timings[groups.find(i)]
				groups.union(i, right_i)
				timings[groups.find(i)] = min(self_t, right_t)
		y_line = mines_by_y[y]
		if len(y_line) > 1:
			lower = 0
			upper = len(y_line)
			while upper - lower > 1:
				candidate = (upper + lower) // 2
				if y_line[candidate][0] <= x:
					lower = candidate
				else:
					upper = candidate
			if lower > 0 and x - y_line[lower - 1][0] <= k:
				left_i = y_line[lower - 1][2]
				left_t = timings[groups.find(left_i)]
				self_t = timings[groups.find(i)]
				groups.union(i, left_i)
				timings[groups.find(i)] = min(self_t, left_t)
			if lower < len(y_line) - 1 and y_line[lower + 1][0] - x <= k:
				right_i = y_line[lower + 1][2]
				right_t = timings[groups.find(right_i)]
				self_t = timings[groups.find(i)]
				groups.union(i, right_i)
				timings[groups.find(i)] = min(self_t, right_t)
	final_timings = []
	for i in range(n):
		if i == groups.find(i):
			final_timings.append(timings[i])
	final_timings.sort(reverse=True)
	answer = 0
	while answer < len(final_timings) - 1 and final_timings[answer + 1] > answer:
		answer += 1
	stdout.write(str(answer) + '\n')