#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define endl '\n'
using i128 = __int128;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const i64 inf = 2e18;
//-------------------------------------------

struct st_tree
{
    int n;
    vector<int> p;
    st_tree(int _n) : p(_n + 1), n(_n) {};

    void init(int _n)
    {
        for (int i = 1; i <= n; i++)
            p[i] = 0;
        n = _n;
    }

    int lowbit(int x)
    {
        return x & -x;
    }

    void add(int u, int d)
    {
        while (u <= n)
            p[u] += d, u += lowbit(u);
    }

    int find(int u)
    {
        int sum = 0;
        while (u > 0)
        {
            sum += p[u], u -= lowbit(u);
        }
        return sum;
    }
};

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        a[i] = a[i] - i;
    }

    int num = *min_element(a.begin(), a.end());
    vector<int> hx;
    if (num <= 0)
    {
        num = abs(num);
        for (int i = 1; i <= n; i++)
        {
            a[i] += num + 1;
        }
    }
    hx.push_back(-1);
    for (int i = 1; i <= n; i++)
    {
        hx.push_back(a[i]);
    }
    sort(hx.begin(), hx.end());
    hx.erase(unique(hx.begin(), hx.end()), hx.end());

    auto find = [&](int num)
    {
        return lower_bound(hx.begin(), hx.end(), num) - hx.begin();
    };

    int m = hx.size() - 1;
    st_tree stt(m), cnt(m);

    auto cal = [&](int x, int mid)
    {
        int id = find(x);
        int sum = 0;
        sum += cnt.find(id - 1) * mid - stt.find(id - 1);
        sum += (stt.find(m) - stt.find(id - 1)) - (cnt.find(m) - cnt.find(id - 1)) * mid;
        return sum;
    };

    auto check = [&](int x)
    {
        int sum = 0;
        stt.init(m);
        cnt.init(m);
        // cerr << x << endl;
        for (int r = 1; r <= n; r++)
        {
            int id = find(a[r]);
            sum += a[r];
            stt.add(id, a[r]);
            cnt.add(id, 1);
            if (r >= x)
            {
                int midl = sum / x, midr = sum / x + 1;
                int w = min(cal(midl, midl), cal(midr, midr));
                // cerr << w << " " << r << endl;
                if (w <= k)
                    return true;
                int idl = find(a[r - x + 1]);
                sum -= a[r - x + 1];
                stt.add(idl, -a[r - x + 1]);
                cnt.add(idl, -1);
            }
        }
        return false;
    };

    int l = 1, r = n;
    check(2);
    while (r > l)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    cout << l << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; i++)
        solve();
    return 0;
}