human
Write me a 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 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...
Solve the task in PYTHON3.
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.

import io,os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):

    s = input()
    n,k = map(int,input().split())
    
    group = [i for i in range(n)] 
    mintime = []  

    dicx = {}
    dicy = {}


    for i in range(n):
        x,y, time = map(int,input().split())
        if x not in dicx:  dicx[x] = []
        dicx[x].append([y,i])
        if y not in dicy:  dicy[y] = []
        dicy[y].append([x,i])
        mintime.append(time)

#    print(dicx)

    for key in dicx:  dicx[key].sort()
    for key in dicy:  dicy[key].sort()

    
    def unionfind(root):
        son = root 
        while root!=group[root]:
            root = group[root]
        while son!=root:
            temp = group[son]
            group[son] = root
            son = group[temp]
        return root

#    print(dicx,dicy)

    for key in dicx:
        arr = dicx[key]
        for i in range(len(arr)-1):
            if arr[i+1][0]-arr[i][0] > k: continue 

            root1,root2 = arr[i][1],arr[i+1][1]
            root1 = unionfind(root1)
            root2 = unionfind(root2)
            if root1==root2: continue 
            group[max(root1,root2)] = min(root1,root2)

    for key in dicy:
        arr = dicy[key]
        for i in range(len(arr)-1):
            if arr[i+1][0]-arr[i][0] > k: continue 

            root1,root2 = arr[i][1],arr[i+1][1]
            root1 = unionfind(root1)
            root2 = unionfind(root2)
            if root1==root2: continue 
            group[max(root1,root2)] = min(root1,root2)

    for i in range(n):
        group[i] = group[unionfind(i)]
        mintime[group[i]] = min(mintime[group[i]],  mintime[i])


    grouptime = []
    for i in range(n):
        if i==group[i]:  grouptime.append(mintime[i])
    
    

    grouptime.sort()

    ans = 0
    
    for i in range(len(grouptime)):
        ans = max(ans, min( grouptime[i], len(grouptime)-i-1  ) )

    print(ans)













T = int(input())
t = 1
while t<=T:
    main(t)
    t += 1