description: 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
  
  <image> Picture from examples
  
  First example: 
  
    * 0 second: we explode a mine at the cell (2, 2), it does not detonate any other mine since k=0. 
    * 1 second: we explode the mine at the cell (0, 1), and the mine at the cell (0, 0) explodes itself. 
    * 2 second: we explode the mine at the cell (1, 1), and the mine at the cell (1, 0) explodes itself.
  
  
  
  Second example:
  
    * 0 second: we explode a mine at the cell (2, 2) we get: 
  
  <image>
  
    * 1 second: the mine at coordinate (0, 0) explodes and since k=2 the explosion detonates mines at the cells (0, 1) and (1, 0), and their explosions detonate the mine at the cell (1, 1) and there are no mines left on the field. 
solution: import java.util.*;
  import java.io.*;
  
  ////***************************************************************************
   /* public class E_Gardener_and_Tree implements Runnable{
  
         public static void main(String[] args) throws Exception {
          new Thread(null, new E_Gardener_and_Tree(), "E_Gardener_and_Tree", 1<<28).start();
         }
      public void run(){
           WRITE YOUR CODE HERE!!!!
           JUST WRITE EVERYTHING HERE WHICH YOU WRITE IN MAIN!!!
         }
  
    }
  */
  /////**************************************************************************
  
  
  public class G_Unusual_Minesweeper{
      public static void main(String[] args) {
          FastScanner s= new FastScanner();
          //PrintWriter out=new PrintWriter(System.out);
          //end of program
          //out.println(answer);
          //out.close();
          StringBuilder res = new StringBuilder();
          int t=s.nextInt();
          int p=0;
          while(p<t){
          
          int n=s.nextInt();
          long k=s.nextLong();
          ArrayList<node> list = new ArrayList<node>(n+2);// nodes are numbered from 0 to n-1
          yoyo obj2 = new yoyo();
          PriorityQueue<node> well = new PriorityQueue<node>(obj2);
          for(int i=0;i<n;i++){
              long a=s.nextLong();
              long b=s.nextLong();
              long c=s.nextLong();
              node obj =new node(a,b,c,i);
              list.add(obj);
              well.add(obj);
          }
          ArrayList<node> sorted = new  ArrayList<node>(n+4);// contains sorted list on the basisi of time
          while(well.size()>0){
              sorted.add(well.poll());
          }
          ArrayList<ArrayList<Integer>> nice = new  ArrayList<ArrayList<Integer>>(n+3);// graph
          for(int i=0;i<n;i++){
              ArrayList<Integer> obj3 = new  ArrayList<Integer>();
              nice.add(obj3);
          }
          make1(list,nice,n);
          make2(list,nice,n);
          long start=-1;
          long end=power(10,9)+10;
          long mid=0;
          while(start<end){
              mid=(start+end)/2;
              if(start+1==end){
                  break;
              }
              int visited[]= new int[n];
              int temp=0;
              for(int i=0;i<n;i++){
                  node obj11 = sorted.get(i);
                  if(obj11.array[2]<=mid){
                       if(visited[(int)(obj11.array[3])]==0){
                           dfs(list,nice,n,visited,k,(int)(obj11.array[3]));
                       }
                  }
                  else{
                      break;
                  }
                  temp++;
              }
              long val=0;
              for(;temp<n;temp++){
                  node obj11 = sorted.get(temp);
                  if(visited[(int)(obj11.array[3])]==0){
                      val++;
                      dfs(list,nice,n,visited,k,(int)(obj11.array[3]));
                  }
  
              }
              long yo=mid+1;
              if(val<=yo){
                  end=mid;
              }
              else{
                  start=mid;
              }
  
          }
          res.append(end+" \n");
          p++;
      }
      System.out.println(res);
  
  
  
         
  
  
      }
      private static void dfs(ArrayList<node> list, ArrayList<ArrayList<Integer>> nice, int n,
              int[] visited, long k, int i) {
                  visited[i]=1;
                  node obj=list.get(i);// curr node
                  for(int j=0;j<nice.get(i).size();j++){
                      int num=nice.get(i).get(j);//num mai node's number
                      node obj4 = list.get(num);
                      if(obj.array[0]==obj4.array[0]){// same x- co-ordinate
                           long a1=obj.array[1];
                           long a2=obj4.array[1];
                           long a3=Math.abs(a1-a2);
                             if(a3<=k && visited[num]==0){
                                 dfs(list,nice,n,visited,k,num);
                             }
                      }
                      else{// same y-co-ordinate
                          long a1=obj.array[0];
                          long a2=obj4.array[0];
                          long a3=Math.abs(a1-a2);
                            if(a3<=k && visited[num]==0){
                                dfs(list,nice,n,visited,k,num);
                            }
  
                      }
  
  
  
                  }
  
      }
  
      private static void make2(ArrayList<G_Unusual_Minesweeper.node> list, ArrayList<ArrayList<Integer>> nice, int n) {
      
                   
                         // fix the y co-ordinate
                 ArrayList<ArrayList<node>> well = new  ArrayList<ArrayList<node>>();
                 HashMap<Long,Long> map = new HashMap<Long,Long>();
                 for(int i=0;i<n;i++){
                     node obj1 = list.get(i);
                     long y=obj1.array[1];
                     if(map.containsKey(y)){
                         long yo=map.get(y);
                         well.get((int)yo).add(obj1);
                     }
                     else{
                         int hh=well.size();
                         ArrayList<node> obj3 = new  ArrayList<node>();
                         obj3.add(obj1);
                         well.add(obj3);
                         map.put(y,(long)hh);
                     }
                 }
  
                 yoyo3 obj6 = new yoyo3();
  
                 for(int i=0;i<well.size();i++){
                     ArrayList<node> obj5 = well.get(i);
                     PriorityQueue<node> hh = new PriorityQueue<node>(obj6);
                      for(int j=0;j<obj5.size();j++){
                          hh.add(obj5.get(j));
                      }
  
                      ArrayList<node> obj7 = new  ArrayList<node>(hh.size()+2);
                      while(hh.size()>0){
                          obj7.add(hh.poll());
                      }
                      for(int j=0;j<obj7.size()-1;j++){
                          node obja=obj7.get(j);
                          node objb = obj7.get(j+1);
                          int a=(int)(obja.array[3]);
                          int b=(int)(objb.array[3]);
                          nice.get(a).add(b);
                          nice.get(b).add(a);
                      }
  
                 }
      }
      private static void make1(ArrayList<node> list, ArrayList<ArrayList<Integer>> nice, int n) {
                 // fix the x co-ordinate
                 ArrayList<ArrayList<node>> well = new  ArrayList<ArrayList<node>>();
                 HashMap<Long,Long> map = new HashMap<Long,Long>();
                 for(int i=0;i<n;i++){
                     node obj1 = list.get(i);
                     long x=obj1.array[0];
                     if(map.containsKey(x)){
                         long yo=map.get(x);
                         well.get((int)yo).add(obj1);
                     }
                     else{
                         int hh=well.size();
                         ArrayList<node> obj3 = new  ArrayList<node>();
                         obj3.add(obj1);
                         well.add(obj3);
                         map.put(x,(long)hh);
                     }
                 }
  
                 yoyo2 obj6 = new yoyo2();
  
                 for(int i=0;i<well.size();i++){
                     ArrayList<node> obj5 = well.get(i);
                     PriorityQueue<node> hh = new PriorityQueue<node>(obj6);
                      for(int j=0;j<obj5.size();j++){
                          hh.add(obj5.get(j));
                      }
  
                      ArrayList<node> obj7 = new  ArrayList<node>(hh.size()+2);
                      while(hh.size()>0){
                          obj7.add(hh.poll());
                      }
                      for(int j=0;j<obj7.size()-1;j++){
                          node obja=obj7.get(j);
                          node objb = obj7.get(j+1);
                          int a=(int)(obja.array[3]);
                          int b=(int)(objb.array[3]);
                          nice.get(a).add(b);
                          nice.get(b).add(a);
                      }
  
                 }
               
      }
      static class FastScanner {
  		BufferedReader br;
  		StringTokenizer st;
   
  		public FastScanner(String s) {
  			try {
  				br = new BufferedReader(new FileReader(s));
  			} catch (FileNotFoundException e) {
  				// TODO Auto-generated catch block
  				e.printStackTrace();
  			}
  		}
   
  		public FastScanner() {
  			br = new BufferedReader(new InputStreamReader(System.in));
  		}
   
  		String nextToken() {
  			while (st == null || !st.hasMoreElements()) {
  				try {
  					st = new StringTokenizer(br.readLine());
  				} catch (IOException e) {
  					// TODO Auto-generated catch block
  					e.printStackTrace();
  				}
  			}
  			return st.nextToken();
  		}
   
  		int nextInt() {
  			return Integer.parseInt(nextToken());
  		}
   
  		long nextLong() {
  			return Long.parseLong(nextToken());
  		}
   
  		double nextDouble() {
  			return Double.parseDouble(nextToken());
  		}
  	}
  
  
      static long modpower(long x, long y, long p)
       {
        long res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        if (x == 0)
          return 0; // In case x is divisible by p;
     
        while (y > 0)
        {
     
          // If y is odd, multiply x with result
          if ((y & 1) != 0)
            res = (res * x) % p;
     
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
        }
        return res;
      }
  
    
     // SIMPLE POWER FUNCTION=>
  
  
        static long power(long x, long y)
          {
              long res = 1;     // Initialize result
          
              while (y > 0)
              {
              
                  // If y is odd, multiply x with result
                  if ((y & 1) != 0)
                      res = res * x;
          
                  // y must be even now
                  y = y >> 1; // y = y/2
                  x = x * x;  // Change x to x^2
              }
              return res;
          }
  
          static class node{
              long array[];
              node(long a, long b, long c, long d){
                  array= new long[4];
                  array[0]=a;
                  array[1]=b;
                  array[2]=c;
                  array[3]=d;
              }
          }
  
          static class yoyo implements Comparator<node>{
  
             
              public int compare(node o1, node o2) {
                  // TODO Auto-generated method stub
                   if(o1.array[2]<=o2.array[2]){
                       return -1;
                   }
                   else{
                       return 1;
                   }
              }
              
          }
  
          static class yoyo2 implements Comparator<node>{
  
              
              public int compare(node o1, node o2) {
                  // TODO Auto-generated method stub
                  if(o1.array[1]<=o2.array[1]){
                      return -1;
                  }
                  else{
                      return 1;
                  }
              }
  
          }
  
          static class yoyo3 implements Comparator<node>{
  
              
              public int compare(node o1, node o2) {
                  // TODO Auto-generated method stub
                  if(o1.array[0]<=o2.array[0]){
                      return -1;
                  }
                  else{
                      return 1;
                  }
              }
  
          }
  
  
  
  
  }