human
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 ≤ t ≤ 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 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ k ≤ 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 ≤ x, y ≤ 10^9, 0 ≤ timer ≤ 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 ⋅ 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.

Example

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...
from
assistant
#Here is Python code to 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.
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)