#include<bits/stdc++.h>

#define int long long

using namespace std;

const int maxn=1000500;
int n,a[maxn],b[maxn*3],m,sum[maxn],q;
int deleted[maxn];

struct segment_tree{
    struct tree{
        int val,size;
    }t[maxn*3*4];

    #define lson i<<1,l,mid
    #define rson i<<1|1,mid+1,r
    #define ls i<<1
    #define rs i<<1|1

    void pushup(int i)
    {
        t[i].size=t[ls].size+t[rs].size;
        t[i].val=t[ls].val+t[rs].val;
    }

    void rebuild_tree(int i,int l,int r)
    {
        t[i].size=t[i].val=0;
        if(l==r) return ;
        int mid=(l+r)/2;
        rebuild_tree(lson);
        rebuild_tree(rson);
        return ;
    }

    void change_tree(int i,int l,int r,int x,int targetval,int targetsize)
    {
        if(x<l||x>r) return ;
        if(l==r)
        {
            t[i].size+=targetsize;
            t[i].val+=targetval;
            return ;
        }
        int mid=(l+r)/2;
        if(x<=mid) change_tree(lson,x,targetval,targetsize);
        else change_tree(rson,x,targetval,targetsize);
        pushup(i);
    }

    pair<int,int> ask_sum_tree(int i,int l,int r,int x,int y)
    {
        if(l>r) return make_pair(0,0);
        if(x>y) return make_pair(0,0);
        if(l>=x&&r<=y)
        {
            return make_pair(t[i].val,t[i].size);
        }
        int mid=(l+r)/2;
        pair<int,int> ans1=make_pair(0,0),ans2=make_pair(0,0);
        if(x<=mid) ans1=ask_sum_tree(lson,x,y);
        if(y>mid) ans2=ask_sum_tree(rson,x,y);
        ans1.first+=ans2.first;
        ans1.second+=ans2.second;
        return ans1;
    }

}st;

void solve()
{
    scanf("%lld %lld",&n,&q);
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&a[i]);
        b[i+n]=a[i]-i+1,b[i+n+n]=a[i]-i-1,b[i]=a[i]-i;
        sum[i]=sum[i-1]+a[i];
    }
    sort(b+1,b+3*n+1);
    memset(deleted,0,sizeof(int)*(n+20));
    m=unique(b+1,b+n*3+1)-b;
    st.rebuild_tree(1,1,m);
    auto checkvalue= [&](int x,int place)
    {
        int targetplace=upper_bound(b+1,b+m+1,x-place)-b;
        pair<int,int> tmp=st.ask_sum_tree(1,1,m,1,targetplace-1);
        int val=-tmp.first+tmp.second*(x-place);
        tmp=st.ask_sum_tree(1,1,m,targetplace,m);
        val+=tmp.first-tmp.second*(x-place);
        return val<=q;
    };
    auto check = [&](int len)->
    int {
        for(int i=1;i<=n;i++) 
        {
            if(deleted[i]!=1) continue;
            int vp=lower_bound(b+1,b+m+1,a[i]-i)-b;
            st.change_tree(1,1,m,vp,-a[i]+i,-1);
            deleted[i]=0;
        }
        for(int i=1;i<=len;i++)
        {
            int vp=lower_bound(b+1,b+m+1,a[i]-i)-b;
            st.change_tree(1,1,m,vp,a[i]-i,1);
            deleted[i]=1;
        }
        if(checkvalue(sum[len]/len,(len)/2+1)) return 1;
        if(checkvalue(sum[len]/len,(len)/2)) return 1;
        for(int i=len+1;i<=n;i++)
        {
            int vp=lower_bound(b+1,b+m+1,a[i]-i)-b;
            st.change_tree(1,1,m,vp,a[i]-i,1);
            vp=lower_bound(b+1,b+m+1,a[i-len]-(i-len))-b;
            st.change_tree(1,1,m,vp,-a[i-len]+(i-len),-1);
            deleted[i]=1;
            deleted[i-len]=0;
            if(checkvalue((sum[i]-sum[i-len])/len,i-(len+1)/2+1)) return 1;
            if(checkvalue((sum[i]-sum[i-len])/len,i-(len+1)/2)) return 1;
        }
        return 0;
    };

    auto getans = [&]()
    {
        int l=1,r=n,mid,ans=0;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(check(mid)) ans=mid,l=mid+1;
            else r=mid-1;
        }
        return ans;
    };
    printf("%lld\n",getans());
}

signed main()
{
    // ios::sync_with_stdio(false);
    int T;
    scanf("%lld",&T);
    // cin>>T; 
    while(T--) 
    {
        solve();
    }
}

/*
1
6 0
100 3 4 5 99 100
*/

/*
1
5 6
1 1 1 1 1 
*/