human
Can you solve the below in PYTHON3?
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...
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.

# Codeforces Round #762 (Div. 3)
# G. Unusual Minesweeper

import collections

class DisjointSet:

    def __init__(self, init):
        # Dictionary where d[x] = [x.parent, x.size]
        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()))]

    # Store all points by their x and y coordinates
    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

    # Create disjoint set, join points if their x or y coords differ by <= k
    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])

    # Map of index i -> min timer in component i
    comp_time = collections.defaultdict(lambda: 1e10)
    for i in range(n):
        f = DS.find(i)
        comp_time[f] =...