#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const double pi = 3.14159265358979323846;
const long long mxN = 2e5 + 1;
void _print(long long t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(double t) { cerr << t; }
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
map<pair<long long, long long>, long long> id;
map<long long, long long> minn;
map<long long, long long> par;
long long find(long long x) {
  if (par[x] == x) return x;
  return par[x] = find(par[x]);
}
void merge(long long x, long long y) {
  long long fx = find(x);
  long long fy = find(y);
  if (fx == fy) return;
  par[fx] = fy;
  minn[fy] = min(minn[fy], minn[fx]);
}
bool cmp(pair<long long, long long>& a, pair<long long, long long>& b) {
  if (a.first == b.first) return a.second < b.second;
  return a.first < b.first;
}
bool cmp1(pair<long long, long long>& a, pair<long long, long long>& b) {
  if (a.second == b.second) return a.first < b.first;
  return a.second < b.second;
}
void solve() {
  id.clear();
  minn.clear();
  long long n, k;
  cin >> n >> k;
  vector<pair<long long, long long>> hold;
  for (long long i = 1; i <= n; i++) {
    long long x, y, t;
    cin >> x >> y >> t;
    id[{x, y}] = i;
    minn[i] = t;
    par[i] = i;
    hold.push_back({x, y});
  }
  sort(hold.begin(), hold.end(), cmp);
  for (long long i = 1; i < n; i++) {
    if (hold[i].first == hold[i - 1].first &&
        hold[i].second - hold[i - 1].second <= k)
      merge(id[hold[i]], id[hold[i - 1]]);
  }
  sort(hold.begin(), hold.end(), cmp1);
  for (long long i = 1; i < n; i++) {
    if (hold[i].second == hold[i - 1].second &&
        hold[i].first - hold[i - 1].first <= k)
      merge(id[hold[i]], id[hold[i - 1]]);
  }
  set<long long> finalid;
  for (long long i = 1; i <= n; i++) {
    if (par[i] == i) finalid.insert(i);
  }
  vector<pair<long long, long long>> fin;
  for (auto x : finalid) fin.push_back({minn[x], x});
  sort(fin.begin(), fin.end());
  ;
  long long f = 0, e = fin.size() - 1;
  long long time = -1;
  while (f <= e) {
    time++;
    e--;
    while (f < fin.size() && fin[f].first <= time) f++;
  }
  cout << time << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

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. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const double pi = 3.14159265358979323846;
const long long mxN = 2e5 + 1;
void _print(long long t) { cerr << t; }
void _print(string t) { cerr << t; }
void _print(char t) { cerr << t; }
void _print(double t) { cerr << t; }
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p) {
  cerr << "{";
  _print(p.first);
  cerr << ",";
  _print(p.second);
  cerr << "}";
}
template <class T>
void _print(vector<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(set<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T>
void _print(multiset<T> v) {
  cerr << "[ ";
  for (T i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
template <class T, class V>
void _print(map<T, V> v) {
  cerr << "[ ";
  for (auto i : v) {
    _print(i);
    cerr << " ";
  }
  cerr << "]";
}
map<pair<long long, long long>, long long> id;
map<long long, long long> minn;
map<long long, long long> par;
long long find(long long x) {
  if (par[x] == x) return x;
  return par[x] = find(par[x]);
}
void merge(long long x, long long y) {
  long long fx = find(x);
  long long fy = find(y);
  if (fx == fy) return;
  par[fx] = fy;
  minn[fy] = min(minn[fy], minn[fx]);
}
bool cmp(pair<long long, long long>& a, pair<long long, long long>& b) {
  if (a.first == b.first) return a.second < b.second;
  return a.first < b.first;
}
bool cmp1(pair<long long, long long>& a, pair<long long, long long>& b) {
  if (a.second == b.second) return a.first < b.first;
  return a.second < b.second;
}
void solve() {
  id.clear();
  minn.clear();
  long long n, k;
  cin >> n >> k;
  vector<pair<long long, long long>> hold;
  for (long long i = 1; i <= n; i++) {
    long long x, y, t;
    cin >> x >> y >> t;
    id[{x, y}] = i;
    minn[i] = t;
    par[i] = i;
    hold.push_back({x, y});
  }
  sort(hold.begin(), hold.end(), cmp);
  for (long long i = 1; i < n; i++) {
    if (hold[i].first == hold[i - 1].first &&
        hold[i].second - hold[i - 1].second <= k)
      merge(id[hold[i]], id[hold[i - 1]]);
  }
  sort(hold.begin(), hold.end(), cmp1);
  for (long long i = 1; i < n; i++) {
    if (hold[i].second == hold[i - 1].second &&
        hold[i].first - hold[i - 1].first <= k)
      merge(id[hold[i]], id[hold[i - 1]]);
  }
  set<long long> finalid;
  for (long long i = 1; i <= n; i++) {
    if (par[i] == i) finalid.insert(i);
  }
  vector<pair<long long, long long>> fin;
  for (auto x : finalid) fin.push_back({minn[x], x});
  sort(fin.begin(), fin.end());
  ;
  long long f = 0, e = fin.size() - 1;
  long long time = -1;
  while (f <= e) {
    time++;
    e--;
    while (f < fin.size() && fin[f].first <= time) f++;
  }
  cout << time << '\n';
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  long long T = 1;
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

```