#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;
    }
};

// root 是最终平衡树,x,y,z记录中间出现的平衡树，idx 是节点编号

struct fhq_treap
{
    struct node
    {
        int l, r, cnt, key, size;
    };
    int x = 0, y = 0, z = 0, root = 0, idx = 0;
    vector<node> fhq;
    fhq_treap(int n) : fhq(n + 1) {};
    int newnode(int cnt)
    {
        fhq[++idx].cnt = cnt;
        fhq[idx].key = rand();
        fhq[idx].size = 1;
        return idx;
    }

    void update(int now)
    {
        fhq[now].size = fhq[fhq[now].l].size + fhq[fhq[now].r].size + 1; // 不要忘记加1 (父节点)
    }

    void spilt(int now, int val, int &x, int &y)
    {
        if (!now)
            x = y = 0;
        else
        {
            if (fhq[now].cnt <= val) // 因为当前节点的值小于val，故当前节点和其全部左子树全部被割个了x
            {
                x = now;
                spilt(fhq[now].r, val, fhq[now].r, y);
            }
            else
            {
                y = now;
                spilt(fhq[now].l, val, x, fhq[now].l);
            }
            update(now);
        }
    }

    int merge(int x, int y) // 注意 y树的所有元素要严格大于x树
    {
        if (!x || !y)
            return x + y;
        else
        {
            if (fhq[x].key <= fhq[y].key) // 无所谓，反正key是随机的
            {
                fhq[y].l = merge(x, fhq[y].l);
                update(y);
                return y;
            }
            else
            {
                fhq[x].r = merge(fhq[x].r, y);
                update(x);
                return x;
            }
        }
    }

    void ins(int val)
    {
        spilt(root, val, x, y);
        root = merge(merge(x, newnode(val)), y);
    }

    void del(int val)
    {
        spilt(root, val, x, y);
        spilt(x, val - 1, x, z); // 此时便把所有等于val的值抛离出来成为z树
        z = merge(fhq[z].l, fhq[z].r);
        root = merge(merge(x, z), y);
    }

    int getrank(int val)
    {
        spilt(root, val - 1, x, y);
        return fhq[x].size + 1;
        root = merge(x, y);
    }

    int getnum(int k)
    {
        int now = root;
        while (now)
        {
            if (fhq[fhq[now].l].size + 1 == k)
                break;
            if (fhq[fhq[now].l].size >= k)
                now = fhq[now].l;
            else
            {
                k -= fhq[fhq[now].l].size + 1; // 不要忘记把根节点减去
                now = fhq[now].r;
            }
        }
        return fhq[now].cnt;
    }

    int pre(int val)
    {
        spilt(root, val - 1, x, y);
        int now = x;
        while (fhq[now].r)
            now = fhq[now].r;
        return fhq[now].cnt;
        root = merge(x, y);
    }

    int nxt(int val)
    {
        spilt(root, val, x, y);
        int now = y;
        while (fhq[now].l)
            now = fhq[now].l;
        return fhq[now].cnt;
        root = merge(x, y);
    }
};

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);
        fhq_treap fhq(2 * n);
        for (int r = 1; r <= n; r++)
        {
            int id = find(a[r]);
            sum += a[r];
            stt.add(id, a[r]);
            cnt.add(id, 1);
            fhq.ins(a[r]);
            if (r >= x)
            {
                int midl = fhq.getnum(x / 2), midr = fhq.getnum(x / 2 + 1);
                int w = min(cal(midl, midl), cal(midr, midr));
                if (w <= k)
                    return true;
                int id = find(a[r - x + 1]);
                sum -= a[r - x + 1];
                stt.add(id, -a[r - x + 1]);
                cnt.add(id, -1);
                fhq.del(a[r - x + 1]);
            }
        }
        return false;
    };

    int l = 1, r = n;
    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;
}