#include <bits/stdc++.h>
using namespace std;
void setup();
void sieve();
long long pow();
long long powm(long long x, long long y, long long m);
bool isprime();
long long modInverse();
vector<long long> prime;
static const long long MOD[2] = {998244353, 1000000007};
struct Node {
 public:
  long long TODO;
  long long val;
  bool todo;
  Node(long long _val) : val(_val) {
    TODO = 1;
    todo = 0;
  }
  void set_todo(long long x) { TODO = x; }
  void set_val(long long x) { val = x; }
  void update_val(long long x) { val = x; }
  void update_todo(long long x, long long int left, long long int right) {
    todo = 1;
    TODO *= x;
    TODO %= MOD[1];
    long long new_val = (x % MOD[1] * val % MOD[1]) % MOD[1];
    set_val(new_val % MOD[1]);
  }
};
class SegmentTree {
 public:
  vector<Node> seg_tree;
  long long int n;
  vector<long long> arr;
  Node useless_node = {0};
  SegmentTree(vector<long long>& _arr, long long int _n,
              long long default_value) {
    n = _n;
    arr = _arr;
    seg_tree.resize(4 * n, {default_value});
    useless_node.set_val(default_value);
    build(1, n, 1);
  }
  void build(long long int left, long long int right, long long int idx) {
    if (left == right)
      seg_tree[idx].set_val(arr[left]);
    else {
      long long int mid = (left + right) >> 1;
      build(left, mid, idx << 1);
      build(mid + 1, right, (idx << 1) + 1);
      seg_tree[idx] = combine(seg_tree[idx << 1], seg_tree[(idx << 1) + 1]);
    }
  }
  Node combine(Node left, Node right) { return Node((left.val + right.val)); }
  Node query(long long int l, long long int r) { return query(1, n, 1, l, r); }
  Node query(long long int left, long long int right, long long int idx,
             long long int l, long long int r) {
    if (right < l or left > r) return useless_node;
    if (l <= left and right <= r) return seg_tree[idx];
    long long int mid = (left + right) >> 1;
    push(idx, left, right, mid);
    return combine(query(left, mid, idx << 1, l, r),
                   query(mid + 1, right, (idx << 1) + 1, l, r));
  }
  void point_update(long long int i, long long val) {
    point_update(1, n, 1, val, i);
  }
  void point_update(long long int left, long long int right, long long int idx,
                    long long val, long long int i) {
    if (left == right)
      seg_tree[idx].update_val(val);
    else {
      long long int mid = (left + right) >> 1;
      push(idx, left, right, mid);
      if (i <= mid)
        point_update(left, mid, idx << 1, val, i);
      else
        point_update(mid + 1, right, (idx << 1) + 1, val, i);
      seg_tree[idx] = combine(seg_tree[idx << 1], seg_tree[(idx << 1) + 1]);
    }
  }
  void range_update(long long int left, long long int right, long long int idx,
                    long long int l, long long int r, long long val) {
    if (right < l or left > r) return;
    long long int mid = (left + right) >> 1;
    push(idx, left, right, mid);
    if (l <= left and right <= r) {
      seg_tree[idx].update_todo(val, left, right);
      return;
    }
    range_update(left, mid, idx << 1, l, r, val);
    range_update(mid + 1, right, (idx << 1) + 1, l, r, val);
    seg_tree[idx] = combine(seg_tree[idx << 1], seg_tree[(idx << 1) + 1]);
  }
  void range_update(long long int l, long long int r, long long val) {
    range_update(1, n, 1, l, r, val);
  }
  void push(long long int idx, long long int left, long long int right,
            long long int mid) {
    if (seg_tree[idx].todo) {
      if (left == right) {
      } else {
        seg_tree[idx << 1].update_todo(seg_tree[idx].TODO, left, mid);
        seg_tree[(idx << 1) + 1].update_todo(seg_tree[idx].TODO, mid + 1,
                                             right);
      }
      seg_tree[idx].todo = 0;
      seg_tree[idx].TODO = 1;
    }
  }
};
string helper(long long int d, long long int s) {
  string ans(d, '0');
  for (long long int i = d - 1; i >= 0; i--) {
    if (s >= 9) {
      ans[i] = '9';
      s -= 9;
    } else {
      char c = (char)s + '0';
      ans[i] = c;
      s = 0;
    }
  }
  return ans;
}
string findMin(long long int x, long long int Y) {
  string y = to_string(Y);
  long long int n = y.size();
  vector<long long int> p(n);
  for (long long int i = 0; i < n; i++) {
    p[i] = y[i] - '0';
    if (i > 0) p[i] += p[i - 1];
  }
  for (long long int i = n - 1, k = 0;; i--, k++) {
    long long int d = 0;
    if (i >= 0) d = y[i] - '0';
    for (long long int j = d + 1; j <= 9; j++) {
      long long int r = (i > 0) * p[i - 1] + j;
      if (x - r >= 0 and x - r <= 9 * k) {
        string suf = helper(k, x - r);
        string pre = "";
        if (i > 0) pre = y.substr(0, i);
        char cur = (char)j + '0';
        pre += cur;
        return pre + suf;
      }
    }
  }
}
void solve() {
  long long n, k;
  cin >> n >> k;
  vector<long long> a(n, 0);
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (long long i = 0; i < n; i++) {
    long long x;
    cin >> x;
  }
  sort(a.begin(), a.end());
  vector<long long> c(n);
  c[n - 1] = 1;
  for (long long i = 0; i < n - 1; i++) {
    auto x = upper_bound(a.begin() + i, a.end(), a[i] + k) - a.begin();
    if (x == n) {
      x--;
    }
    while (a[x] > a[i] + k) x--;
    c[i] = x - i + 1;
  }
  vector<long long> d(n);
  d[n - 1] = 1;
  for (long long i = n - 2; i >= 0; i--) d[i] = max(d[i + 1], c[i]);
  long long ans = 1;
  for (long long i = 0; i < n - 1; i++) {
    auto x = upper_bound(a.begin() + i, a.end(), a[i] + k) - a.begin();
    if (x == n) {
      x--;
    }
    while (a[x] > a[i] + k) x--;
    if (x != n - 1)
      ans = max(x - i + 1 + d[x + 1], ans);
    else
      ans = max(ans, x - i + 1);
  }
  cout << ans;
  cout << "\n";
}
signed main() {
  setup();
  long long int number_of_testcases = 1;
  cin >> number_of_testcases;
  while (number_of_testcases--) solve();
}
void setup() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
void sieve(long long n) {
  prime.resize(n + 5, 0);
  for (long long i = 2; i <= n; i++) {
    if (not prime[i]) {
      prime[i] = i;
      for (long long j = i * i; j <= n; j += i)
        if (not prime[j]) prime[j] = i;
    }
  }
}
long long pow(long long b, long long e) {
  if (e == 0)
    return 1;
  else if (e % 2 == 0) {
    long long a = pow(b, e / 2);
    return a * a;
  } else {
    long long a = pow(b, e / 2);
    return b * a * a;
  }
}
long long powm(long long x, long long y, long long m) {
  x = x % m;
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x;
    res %= m;
    y = y >> 1;
    x = x * x;
    x %= m;
  }
  return res;
}
long long gcd(long long a, long long b) {
  if (a < b)
    return gcd(b, a);
  else if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
bool isprime(long long n) {
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return 0;
  return 1;
}
long long modInverse(long long a, long long m) { return powm(a, m - 2, m); }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (T e : v) os << e << ", ";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
  for (T e : v) os << e << ", ";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  for (T e : v) os << e << ", ";
  return os;
}
template <typename T, typename Y>
ostream& operator<<(ostream& os, const pair<T, Y>& v) {
  os << '{' << v.first << ", " << v.second << "}";
  return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, const map<T, S>& v) {
  for (auto it : v) os << "{" << it.first << ", " << it.second << "}, ";
  return os;
}

### Prompt

Please formulate a cpp solution to the following problem:

There are n points on a plane. The i-th point has coordinates (x_i, y_i). You have two horizontal platforms, both of length k. Each platform can be placed anywhere on a plane but it should be placed horizontally (on the same y-coordinate) and have integer borders. If the left border of the platform is (x, y) then the right border is (x + k, y) and all points between borders (including borders) belong to the platform.

Note that platforms can share common points (overlap) and it is not necessary to place both platforms on the same y-coordinate.

When you place both platforms on a plane, all points start falling down decreasing their y-coordinate. If a point collides with some platform at some moment, the point stops and is saved. Points which never collide with any platform are lost.

Your task is to find the maximum number of points you can save if you place both platforms optimally.

You have to answer t independent test cases.

For better understanding, please read the Note section below to see a picture for the first test case.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ k ≤ 10^9) — the number of points and the length of each platform, respectively. The second line of the test case contains n integers x_1, x_2, ..., x_n (1 ≤ x_i ≤ 10^9), where x_i is x-coordinate of the i-th point. The third line of the input contains n integers y_1, y_2, ..., y_n (1 ≤ y_i ≤ 10^9), where y_i is y-coordinate of the i-th point. All points are distinct (there is no pair 1 ≤ i < j ≤ n such that x_i = x_j and y_i = y_j).

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer: the maximum number of points you can save if you place both platforms optimally.

Example

Input


4
7 1
1 5 2 3 1 5 4
1 3 6 7 2 5 4
1 1
1000000000
1000000000
5 10
10 7 5 15 8
20 199 192 219 1904
10 10
15 19 8 17 20 10 9 2 10 19
12 13 6 17 1 14 7 9 19 3


Output


6
1
5
10

Note

The picture corresponding to the first test case of the example:

<image>

Blue dots represent the points, red segments represent the platforms. One of the possible ways is to place the first platform between points (1, -1) and (2, -1) and the second one between points (4, 3) and (5, 3). Vectors represent how the points will fall down. As you can see, the only point we can't save is the point (3, 7) so it falls down infinitely and will be lost. It can be proven that we can't achieve better answer here. Also note that the point (5, 3) doesn't fall at all because it is already on the platform.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void setup();
void sieve();
long long pow();
long long powm(long long x, long long y, long long m);
bool isprime();
long long modInverse();
vector<long long> prime;
static const long long MOD[2] = {998244353, 1000000007};
struct Node {
 public:
  long long TODO;
  long long val;
  bool todo;
  Node(long long _val) : val(_val) {
    TODO = 1;
    todo = 0;
  }
  void set_todo(long long x) { TODO = x; }
  void set_val(long long x) { val = x; }
  void update_val(long long x) { val = x; }
  void update_todo(long long x, long long int left, long long int right) {
    todo = 1;
    TODO *= x;
    TODO %= MOD[1];
    long long new_val = (x % MOD[1] * val % MOD[1]) % MOD[1];
    set_val(new_val % MOD[1]);
  }
};
class SegmentTree {
 public:
  vector<Node> seg_tree;
  long long int n;
  vector<long long> arr;
  Node useless_node = {0};
  SegmentTree(vector<long long>& _arr, long long int _n,
              long long default_value) {
    n = _n;
    arr = _arr;
    seg_tree.resize(4 * n, {default_value});
    useless_node.set_val(default_value);
    build(1, n, 1);
  }
  void build(long long int left, long long int right, long long int idx) {
    if (left == right)
      seg_tree[idx].set_val(arr[left]);
    else {
      long long int mid = (left + right) >> 1;
      build(left, mid, idx << 1);
      build(mid + 1, right, (idx << 1) + 1);
      seg_tree[idx] = combine(seg_tree[idx << 1], seg_tree[(idx << 1) + 1]);
    }
  }
  Node combine(Node left, Node right) { return Node((left.val + right.val)); }
  Node query(long long int l, long long int r) { return query(1, n, 1, l, r); }
  Node query(long long int left, long long int right, long long int idx,
             long long int l, long long int r) {
    if (right < l or left > r) return useless_node;
    if (l <= left and right <= r) return seg_tree[idx];
    long long int mid = (left + right) >> 1;
    push(idx, left, right, mid);
    return combine(query(left, mid, idx << 1, l, r),
                   query(mid + 1, right, (idx << 1) + 1, l, r));
  }
  void point_update(long long int i, long long val) {
    point_update(1, n, 1, val, i);
  }
  void point_update(long long int left, long long int right, long long int idx,
                    long long val, long long int i) {
    if (left == right)
      seg_tree[idx].update_val(val);
    else {
      long long int mid = (left + right) >> 1;
      push(idx, left, right, mid);
      if (i <= mid)
        point_update(left, mid, idx << 1, val, i);
      else
        point_update(mid + 1, right, (idx << 1) + 1, val, i);
      seg_tree[idx] = combine(seg_tree[idx << 1], seg_tree[(idx << 1) + 1]);
    }
  }
  void range_update(long long int left, long long int right, long long int idx,
                    long long int l, long long int r, long long val) {
    if (right < l or left > r) return;
    long long int mid = (left + right) >> 1;
    push(idx, left, right, mid);
    if (l <= left and right <= r) {
      seg_tree[idx].update_todo(val, left, right);
      return;
    }
    range_update(left, mid, idx << 1, l, r, val);
    range_update(mid + 1, right, (idx << 1) + 1, l, r, val);
    seg_tree[idx] = combine(seg_tree[idx << 1], seg_tree[(idx << 1) + 1]);
  }
  void range_update(long long int l, long long int r, long long val) {
    range_update(1, n, 1, l, r, val);
  }
  void push(long long int idx, long long int left, long long int right,
            long long int mid) {
    if (seg_tree[idx].todo) {
      if (left == right) {
      } else {
        seg_tree[idx << 1].update_todo(seg_tree[idx].TODO, left, mid);
        seg_tree[(idx << 1) + 1].update_todo(seg_tree[idx].TODO, mid + 1,
                                             right);
      }
      seg_tree[idx].todo = 0;
      seg_tree[idx].TODO = 1;
    }
  }
};
string helper(long long int d, long long int s) {
  string ans(d, '0');
  for (long long int i = d - 1; i >= 0; i--) {
    if (s >= 9) {
      ans[i] = '9';
      s -= 9;
    } else {
      char c = (char)s + '0';
      ans[i] = c;
      s = 0;
    }
  }
  return ans;
}
string findMin(long long int x, long long int Y) {
  string y = to_string(Y);
  long long int n = y.size();
  vector<long long int> p(n);
  for (long long int i = 0; i < n; i++) {
    p[i] = y[i] - '0';
    if (i > 0) p[i] += p[i - 1];
  }
  for (long long int i = n - 1, k = 0;; i--, k++) {
    long long int d = 0;
    if (i >= 0) d = y[i] - '0';
    for (long long int j = d + 1; j <= 9; j++) {
      long long int r = (i > 0) * p[i - 1] + j;
      if (x - r >= 0 and x - r <= 9 * k) {
        string suf = helper(k, x - r);
        string pre = "";
        if (i > 0) pre = y.substr(0, i);
        char cur = (char)j + '0';
        pre += cur;
        return pre + suf;
      }
    }
  }
}
void solve() {
  long long n, k;
  cin >> n >> k;
  vector<long long> a(n, 0);
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (long long i = 0; i < n; i++) {
    long long x;
    cin >> x;
  }
  sort(a.begin(), a.end());
  vector<long long> c(n);
  c[n - 1] = 1;
  for (long long i = 0; i < n - 1; i++) {
    auto x = upper_bound(a.begin() + i, a.end(), a[i] + k) - a.begin();
    if (x == n) {
      x--;
    }
    while (a[x] > a[i] + k) x--;
    c[i] = x - i + 1;
  }
  vector<long long> d(n);
  d[n - 1] = 1;
  for (long long i = n - 2; i >= 0; i--) d[i] = max(d[i + 1], c[i]);
  long long ans = 1;
  for (long long i = 0; i < n - 1; i++) {
    auto x = upper_bound(a.begin() + i, a.end(), a[i] + k) - a.begin();
    if (x == n) {
      x--;
    }
    while (a[x] > a[i] + k) x--;
    if (x != n - 1)
      ans = max(x - i + 1 + d[x + 1], ans);
    else
      ans = max(ans, x - i + 1);
  }
  cout << ans;
  cout << "\n";
}
signed main() {
  setup();
  long long int number_of_testcases = 1;
  cin >> number_of_testcases;
  while (number_of_testcases--) solve();
}
void setup() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
void sieve(long long n) {
  prime.resize(n + 5, 0);
  for (long long i = 2; i <= n; i++) {
    if (not prime[i]) {
      prime[i] = i;
      for (long long j = i * i; j <= n; j += i)
        if (not prime[j]) prime[j] = i;
    }
  }
}
long long pow(long long b, long long e) {
  if (e == 0)
    return 1;
  else if (e % 2 == 0) {
    long long a = pow(b, e / 2);
    return a * a;
  } else {
    long long a = pow(b, e / 2);
    return b * a * a;
  }
}
long long powm(long long x, long long y, long long m) {
  x = x % m;
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x;
    res %= m;
    y = y >> 1;
    x = x * x;
    x %= m;
  }
  return res;
}
long long gcd(long long a, long long b) {
  if (a < b)
    return gcd(b, a);
  else if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
bool isprime(long long n) {
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return 0;
  return 1;
}
long long modInverse(long long a, long long m) { return powm(a, m - 2, m); }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (T e : v) os << e << ", ";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& v) {
  for (T e : v) os << e << ", ";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const multiset<T>& v) {
  for (T e : v) os << e << ", ";
  return os;
}
template <typename T, typename Y>
ostream& operator<<(ostream& os, const pair<T, Y>& v) {
  os << '{' << v.first << ", " << v.second << "}";
  return os;
}
template <typename T, typename S>
ostream& operator<<(ostream& os, const map<T, S>& v) {
  for (auto it : v) os << "{" << it.first << ", " << it.second << "}, ";
  return os;
}

```