#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<iomanip>
#include<stack>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<set>
#define ll               long long
#define endl             "\n"
using namespace std;
inline int read() { register int s = 0, w = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-')w = -1; ch = getchar(); }while (ch >= '0' && ch <= '9')s = s * 10 + ch - '0', ch = getchar(); return s * w; }
ll t, n, k, a[500005], b[500005];
const int maxN = 500005;
int roots[maxN];
struct node
{
    int l, r, sum;//这个点的左右节点
    int cl, cr;
}nodes[maxN * 32]; // 32 40 50 64 好像都行
int cnt = 0;//动态权值线段树
ll maxL = 0, maxR = 1000000005;
//pre 上个版本的节点，cur 当前版本的节点，k是插入的数字，l，r是当前维护的区间
void insert(int pre, int& cur, ll k, ll l, ll r) {
    nodes[++cnt] = nodes[pre];
    cur = cnt;
    nodes[cur].cl = l, nodes[cur].cr = r;
    nodes[cur].sum++;
    if (l == r) {
        return;
    }
    ll mid = (l + r) >> 1;
    if (k <= mid) {
        insert(nodes[pre].l, nodes[cur].l, k, l, mid);
    }
    else {
        insert(nodes[pre].r, nodes[cur].r, k, mid + 1, r);
    }
}
//pre是指某一个历史版本的上一个版本；
ll query(int pre, int cur, ll l, ll r, int k) {
    if (l == r) {
        return l;
    }
    ll mid = (l + r) >> 1;
    ll temp = nodes[nodes[cur].l].sum - nodes[nodes[pre].l].sum;
    if (k <= temp) {
        return query(nodes[pre].l, nodes[cur].l, l, mid, k);
    }
    else {
        return query(nodes[pre].r, nodes[cur].r, mid + 1, r, k - temp);
    }
}
bool check(ll len)
{
    ll l = 1, r = len, sum = 0, mi = (1 + len) / 2 - 1, mx = n-(1 + len) / 2;
    for (int i = 1; i <= len; i++)
    {
        insert(roots[i - 1], roots[i], a[i], maxL, maxR);
    }
    ll now = query(roots[0], roots[len], maxL, maxR, (1 + len) / 2), last;
    for (int i = 1; i <= len; i++)
    {
        sum += abs(a[i] - now);
    }
    if (sum <= k)return 1;
    while (r+1 <= n)
    {
        insert(roots[r], roots[r+1], a[r+1], maxL, maxR);
        last = now;
        sum -= abs(a[l] - last);
        if (a[l] < last)
            mi--;
        else
            mx--;
        l++; r++;
        sum += abs(a[r] - last);
        if (a[r] > last)mx++;
        else mi++;
        mi = (len + 1) / 2 - 1;
        mx = len - mi - 1;
        now = query(roots[l - 1], roots[r],maxL, maxR, (len + 1) / 2);
        if (now > last)
        {
            ll tem = query(roots[l - 1], roots[r], maxL, maxR, (len + 1) / 2-1);
            sum += -abs(tem - last) - abs(now - last) + abs(tem - now);
            sum += (now - last) * (mi-1) + (last - now) * (mx);
        }
        else if (now < last)
        {
            ll tem = query(roots[l - 1], roots[r], maxL, maxR, (len + 1) / 2+1);
            sum += -abs(tem - last) - abs(now - last) + abs(tem - now);
            sum += (now - last) * (mi) + (last - now) * (mx-1);
        }
        else
        {
            sum -= abs(a[r] - last);
            sum += abs(a[r] - now);
        }
        if (sum <= k)return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> t;
    ll tt = t;
    while (t--)
    {
        cin >> n >> k;
        ll l = 1, r = n, mid, minn = 1e18;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            a[i] -= i;
            minn = min(minn, a[i]);
        }
        if (minn <= 0)
        {
            for (int i = 1; i <= n; i++)
            {
                a[i] += (-minn) + 1;
            }
        }
        while (l < r)
        {
            mid = (l + r + 1) / 2;
            if (check(mid))l = mid;
            else r = mid - 1;
            for (int i = 1; i <= n; i++)
                roots[i] = 0;
            while (cnt--)
            {
                nodes[cnt + 1].l = nodes[cnt + 1].r = nodes[cnt + 1].sum = nodes[cnt + 1].cl = nodes[cnt + 1].cr = 0;
            }
            cnt = 0;
        }
        cout << l << endl;
    }
    return 0;
}