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

class SDS:
    def __init__(self, n, mins):
        self.n = n
        self.parents = [i for i in range(n)]
        self.mins = mins

    def find(self, i): # find root
        if self.parents[i] != i:
            self.parents[i] = self.find(self.parents[i])
        return self.parents[i]

    def union(self, i, j):
        i, j = self.find(i), self.find(j)
        if i == j:
            return
        self.parents[j] = i
        self.mins[i] = min(self.mins[j], self.mins[i])

    def tolist(self):
        result = []
        for i in range(self.n):
            if i == self.parents[i]:
                result.append(self.mins[i])
        return sorted(result), len(result)

result = []

for _ in range(int(input())):
    input()
    n, k = list(map(int, input().split()))
    mines = [list(map(int, input().split())) + [i] for i in range(n)]
    # create sds
    sds = SDS(n, list(map(lambda x: x[2], mines)))
    # by x
    mines.sort(key=lambda x: (x[0], x[1])) # O(n * log(n))
    i, x, y = None, None, None
    for mine in mines: # O(n * log(n))
        if x == mine[0] and abs(mine[1] - y) <= k:
            sds.union(mine[3], i)
        i, x, y = mine[3], mine[0], mine[1]
    # by y
    mines.sort(key=lambda x: (x[1], x[0])) # O(n * log(n))
    i, x, y = None, None, None
    for mine in mines: # O(n * log(n))
        if y == mine[1] and abs(mine[0] - x) <= k:
            sds.union(mine[3], i)
        i, x, y = mine[3], mine[0], mine[1]
    # find min time in each set
    mins, length = sds.tolist() # O(n * log(n))
    answer = length - 1 # quantity sets
    for i in range(length): # O(n)
        answer = min(answer, max(mins[i], length - i - 2))
    result.append(answer)

print('\n'.join(map(str, result)))