#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

#ifdef LOCAL
#include "algo/debug.h"
#else 
#define debug(...) 42
#endif

struct Node {
  Node *l = nullptr;
  Node *r = nullptr;
  int cnt = 0;
  i64 sum = 0;
  Node() : l{}, r{}, cnt{}, sum{} {}
};

const int N = 5e5;
int L[N + 1], R[N + 1], cnt[N + 1], idx;
i64 sum[N + 1];
inline int newNode() {
  return ++idx;
}

int add(int &t, int l, int r, int x, int v) {
  int nt = newNode();
  L[nt] = L[t];
  R[nt] = R[t];
  cnt[nt] = cnt[t] + 1;
  sum[nt] = sum[t] + v;
  if (r - l > 1) {
    int m = (l + r) / 2;
    if (m > x) {
      L[nt] = add(L[nt], l, m, x, v);
    } else {
      R[nt] = add(R[nt], m, r, x, v);
    }
  }
  return nt;
}

int kth(int &t1, int &t2, int l, int r, int k) {
  if (r - l == 1) {
    return l;
  }
  int ct = cnt[L[t2]] - cnt[L[t1]];
  int m = (l + r) / 2;
  if (ct >= k) {
    return kth(L[t1], L[t2], l, m, k);
  } else {
    return kth(R[t1], R[t2], m, r, k - ct);
  }
}

pair<int, i64> operator+(const pair<int, i64> &lhs, const pair<int, i64> &rhs) {
  return make_pair(lhs.first + rhs.first, lhs.second + rhs.second);
}

pair<int, i64> query(int &t1, int &t2, int l, int r, int x, int y) {
  if (l >= x && r <= y) {
    return make_pair(cnt[t2] - cnt[t1], sum[t2] - sum[t1]);
  }
  if (l >= y || r <= x) {
    return make_pair(0, 0);
  }
  int m = (l + r) / 2;
  return query(L[t1], L[t2], l, m, x, y) + query(R[t1], R[t2], m, r, x, y);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    i64 k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      a[i] -= i;
    }
    auto v = a;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    const int m = (int) v.size();
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
      b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
    }
    idx = 0;
    vector<int> node(n + 1);
    for (int i = 0; i < n; i++) {
      node[i + 1] = add(node[i], 0, m, b[i], a[i]);
    }
    auto calc = [&](int x) {
      i64 ans = 1e18;
      const int s = (x + 1) / 2;
      for (int i = 0; i + x <= n; i++) {
        int p = kth(node[i], node[i + x], 0, m, s);
        auto [c1, s1] = query(node[i], node[i + x], 0, m, 0, p);
        auto [c2, s2] = query(node[i], node[i + x], 0, m, p, m);
        i64 res = 1LL * v[p] * c1 - s1 + s2 - 1LL * v[p] * c2;
        ans = min(ans, res);
      }
      return ans;
    };
    int low = 1, high = n;
    int ans = 1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (calc(mid) <= k) {
        ans = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    cout << ans << '\n';
    for (int i = 1; i <= idx; i++) {
      L[i] = R[i] = cnt[i] = sum[i] = 0;
    }
  }
  return 0; 
}