human
Give me a 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 given the following:
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...
Using python3 can you solve the prior task?
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.

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 = {} # x: (y, t, i)
    mines_by_y = {} # y: (x, t, i)
    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 =...