human
PYTHON3 solution for "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 program 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.
 
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    def find(self, a): #return parent of a. a and b are in same set if they have same parent
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a: #path compression
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
    def union(self, a, b): #union a and 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))
        # first, union all the mines that will explode together
        uf = UnionFind(n) # denote mines by their indexes
        sameCols = defaultdict(lambda:[]) # store rows, mine idx
        sameRows = defaultdict(lambda:[]) # store cols, mine idx
        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(2e9)
        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)
        #...