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...

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?
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
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())