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: /*
          "Everything in the universe is balanced. Every disappointment
                  you face in life will be balanced by something good for you!
                          Keep going, never give up."
  
          "Just have Patience + 1..."
  
  */
  
  
  
  
  import java.util.*;
  import java.lang.*;
  import java.io.*;
  
  public class Solution {
  
      static class Mine {
          int x;
          int y;
          int index;
          Mine (int x, int y, int index) {
              this.x = x;
              this.y = y;
              this.index = index;
          }
      }
  
      static int MAX = 200005;
      static long INF = 100000000000000000L;
      static long[] explosionTime = new long[MAX];
      static Map<Integer, List<Integer>> graph = new HashMap<>();
      static boolean[] visited = new boolean[MAX];
      static int n, k;
      static long minExplosionTime = INF;
  
      public static void main(String[] args) throws java.lang.Exception {
          out = new PrintWriter(new BufferedOutputStream(System.out));
          sc = new FastReader();
  
          int test = sc.nextInt();
          for (int t = 0; t < test; t++) {
              solve();
          }
          out.close();
      }
  
      private static void solve() {
          n = sc.nextInt();
          k = sc.nextInt();
  
          initialize(n);
  
          List<Mine> minesSortedAlongX = new ArrayList<>();
          List<Mine> minesSortedAlongY = new ArrayList<>();
  
          for (int i = 0; i < n; i++) {
              int x = sc.nextInt();
              int y = sc.nextInt();
              explosionTime[i] = sc.nextLong();
  
              minesSortedAlongX.add(new Mine(x, y, i));
              minesSortedAlongY.add(new Mine(y, x, i));
          }
  
          minesSortedAlongX.sort((a, b) -> a.x == b.x ? a.y - b.y : a.x - b.x); // sorting mines according to x - coordinate
          minesSortedAlongY.sort((a, b) -> a.x == b.x ? a.y - b.y : a.x - b.x); // sorting mines according to y - coordinate
  
  
          // build the graph, adding bidirectional edge(u to v) if mine u can detonate mine v.
          // since it may lead to too many edges, we can simplify the edges,
          // so if we can go from mine u to mine (v and z), then we can simplify the edges as from (u to v) and from (v to z), creating edges along a simple path.
  
          addDetonationEdges(minesSortedAlongX); // vertical detonation
          addDetonationEdges(minesSortedAlongY); // horizontal detonation
  
  
          List<Long> stronglyConnectedComponents = new ArrayList<>();
          for (int i = 0; i < n; i++) {
              if (!visited[i]) {
                  minExplosionTime = INF;
                  dfs(i);
                  stronglyConnectedComponents.add(minExplosionTime);
              }
          }
  
          // greedily sorting the mines in descending order, so that mine components with max explosion time can be detonated manually first,
          // and by that time some mine components with lesser explosion time may detonate automatically.
          stronglyConnectedComponents.sort(Collections.reverseOrder());
  
          long minTimeExplodeAllMines = 0;
          for (int i = 0; i < stronglyConnectedComponents.size(); i++) {
              if (stronglyConnectedComponents.get(i) >= i) { // this means we need to manually detonate this mine  at ith second
                  minTimeExplodeAllMines = i;
              }
          }
          out.println(minTimeExplodeAllMines);
      }
  
      private static void addDetonationEdges(List<Mine> mines) {
          for (int i = 1; i < n; i++) {
              if (mines.get(i).x == mines.get(i - 1).x) {
                  long distance = mines.get(i).y - mines.get(i - 1).y;
  
                  if (distance <= k) {
                      int u = mines.get(i).index;
                      int v = mines.get(i - 1).index;
  
                      add(u, v);
                      add(v, u);
                  }
              }
          }
      }
  
      private static void dfs(int currNode) { // find the minimum  explosion time (the time after which it automatically explodes) of a mine in a connected component
          visited[currNode] = true;
          minExplosionTime = Math.min(minExplosionTime, explosionTime[currNode]);
          for (int adjacentNode : graph.get(currNode)) {
              if (!visited[adjacentNode]) {
                  dfs(adjacentNode);
              }
          }
      }
  
      private static void add(int u, int v) {
          if (!graph.containsKey(u)) {
              graph.put(u, new ArrayList<>());
          }
          graph.get(u).add(v);
      }
  
      private static void initialize(int n) {
          graph.clear();
          for (int i = 0; i < n; i++) {
              graph.put(i, new ArrayList<>());
              visited[i] = false;
              explosionTime[i] = INF;
          }
      }
  
  
      public static FastReader sc;
      public static PrintWriter out;
      static class FastReader
      {
          BufferedReader br;
          StringTokenizer str;
  
          public FastReader()
          {
              br = new BufferedReader(new
                      InputStreamReader(System.in));
          }
  
          String next()
          {
              while (str == null || !str.hasMoreElements())
              {
                  try
                  {
                      str = new StringTokenizer(br.readLine());
                  }
                  catch (IOException  end)
                  {
                      end.printStackTrace();
                  }
              }
              return str.nextToken();
          }
  
          int nextInt()
          {
              return Integer.parseInt(next());
          }
  
          long nextLong()
          {
              return Long.parseLong(next());
          }
  
          double nextDouble()
          {
              return Double.parseDouble(next());
          }
  
          String nextLine()
          {
              String str = "";
              try
              {
                  str = br.readLine();
              }
              catch (IOException end)
              {
                  end.printStackTrace();
              }
              return str;
          }
      }
  }