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...
Using python3 can you solve the prior task?
 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?
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 sys;Z=sys.stdin.readline;Y=lambda:map(int,Z().split());X=range;from collections import defaultdict as D
class U:
 def __init__(self,n):self.p=[*X(n)]
 def f(self,a):
  b=a
  while a!=self.p[a]:a=self.p[a]
  while b!=a:self.p[b],b=a,self.p[b]
  return a
O=[];N=10**10
for _ in X(int(Z())):
 Z();n,k=Y();G=D(list);a=[];u=U(n);b=[]
 for i in X(n):x,y,t=Y();a.append(t);G[x].append((y,i));G[y+N].append((x,i))
 for x in G:
  g=G[x];L=len(g);g.sort()
  if L>1:
   for i in X(1,L):
    v=u.f(g[i-1][1]);w=u.f(g[i][1])
    if v!=w and g[i][0]-g[i-1][0]<=k:u.p[w]=v;a[v]=min(a[v],a[w]);a[w]=N
 b=sorted(i for i in a if i<N);c=0
 while c<len(b)-1 and b[-2-c]>c:c+=1
 print(c)