#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 5e5 + 5;
ll n, m, tot, su0, ct0, ctt, k;
int na[N], nb[N];
int _ = 1;
struct node {
    int data;
    ll sum;
} tree[N * 4][20];

// x,y,的cnt个数
// x,y,的sum
void querysum(int id, int l, int r, int ql, int qr, int ctt) {
    if (ql <= l && r <= qr) {
        su0 += tree[id][ctt].sum;
        ct0 += tree[id][ctt].data;
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) {
        querysum(id << 1, l, mid, ql, qr, ctt);
    }
    if (qr > mid) {
        querysum(id << 1 | 1, mid + 1, r, ql, qr, ctt);
    }
}
void change(int id, int l, int r, int x, int cnt, int ctt) {
    if (l == r) {
        tree[id][ctt].data += cnt;
        tree[id][ctt].sum = ll(tree[id][ctt].data) * ll(nb[l]);
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) {
        change(id << 1, l, mid, x, cnt, ctt);
    } else {
        change(id << 1 | 1, mid + 1, r, x, cnt, ctt);
    }
    tree[id][ctt].data = tree[id << 1][ctt].data + tree[id << 1 | 1][ctt].data;
    tree[id][ctt].sum = tree[id << 1][ctt].sum + tree[id << 1 | 1][ctt].sum;
}
// 第cnt个的位置
int querycnt(int id, int l, int r, int cnt, int ctt) {
    if (l == r) {
        return l;
    }
    int mid = l + r >> 1;
    if (cnt > tree[id << 1][ctt].data) {
        return querycnt(id << 1 | 1, mid + 1, r, cnt - tree[id << 1][ctt].data,
                        ctt);
    } else {
        return querycnt(id << 1, l, mid, cnt, ctt);
    }
}

void solve() {
    cin >> n >> k;
    ctt = 0;
    for (int i = 1; i <= n; i++) {
        cin >> na[i];
        na[i] -= i;
        nb[i] = na[i];
    }
    sort(nb + 1, nb + 1 + n);
    int l = 1, r = n;
    for (int i = 1; i <= n; i++) {
        int pos = upper_bound(nb + 1, nb + 1 + n, nb[i]) - nb;
        l = max(l, pos - i + 1);
    }
    tot = unique(nb + 1, nb + 1 + n) - nb - 1;
    for (int i = 1; i <= n; i++) {
        na[i] = lower_bound(nb + 1, nb + 1 + tot, na[i]) - nb;
    }
    auto ck = [&](int mid) -> bool {
        ll res = 0;
        ctt++;
        for (int i = 1; i < mid; i++) {
            change(1, 1, tot, na[i], 1, ctt);
        }
        for (int i = mid; i <= n; i++) {
            change(1, 1, tot, na[i], 1, ctt);
            int pos = querycnt(1, 1, tot, (mid + 1) / 2, ctt);
            ll sum = 0;
            su0 = 0, ct0 = 0;
            if (pos > 1) {
                querysum(1, 1, tot, 1, pos - 1, ctt);
                sum = nb[pos] * ct0 - su0;
                su0 = 0, ct0 = 0;
            }
            querysum(1, 1, tot, pos, tot, ctt);
            sum += su0 - nb[pos] * ct0;
            if (sum <= k) {
                // cout << pos << ' ' << su0 << ' ' << su1;
                return 1;
            }
            change(1, 1, tot, na[i - mid + 1], -1, ctt);
        }

        return 0;
    };

    while (l <= r) {
        int mid = l + r >> 1;
        if (ck(mid)) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << l - 1 << '\n';
    if (_ > 0) {
        for (int i = 1; i <= tot * 4; i++) {
            for (int j = 1; j <= ctt; j++) {
                tree[i][j].data = tree[i][j].sum = 0;
            }
        }
    }
}
int main() {
    std::ios::sync_with_stdio(false);

    std::cin.tie(nullptr);
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}