// duziteng ^ ^
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
const int M = 998244353;
const int mod = 998244353;
#define db double
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
struct node{
    int l,r,v,cnt;
}tr[N<<2];
int n,m;
void pushup(int i){
    auto &u=tr[i],&l=tr[i<<1],&r=tr[i<<1|1];
    u.v=l.v+r.v;
    u.cnt=l.cnt+r.cnt;
}
void build(int i,int l,int r){
    tr[i].l=l,tr[i].r=r,tr[i].cnt=0,tr[i].v=0;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
}
void modify(int i,int x,int k,int k2){
    if(tr[i].l>=x&&tr[i].r<=x){
        auto &u=tr[i];
        u.v+=k;
        u.cnt+=k2;
        return;
    }
    if(tr[i].l>x||tr[i].r<x)return;
    if(tr[i<<1].r>=x)modify(i<<1,x,k,k2);
    if(tr[i<<1|1].l<=x)modify(i<<1|1,x,k,k2);
    pushup(i);
}
int query(int i,int f){
    if(tr[i].l==tr[i].r){
        return tr[i].l;
    }
    if(tr[i<<1].cnt>=f)return query(i<<1,f);
    else{
        return query(i<<1|1,f-tr[i<<1].cnt);
    }
}
PII query(int i,int l,int r){
    PII res={0,0};
    if(tr[i].l>=l&&tr[i].r<=r){
        auto &u=tr[i];
        return {u.v,u.cnt};
    }
    if(tr[i].l>r||tr[i].r<l)return res;
    if(tr[i<<1].r>=l){
        PII now= query(i<<1,l,r);
        res.first+=now.first;
        res.second+=now.second;
    }
    if(tr[i<<1|1].l<=r){
        PII now= query(i<<1|1,l,r);
        res.first+=now.first;
        res.second+=now.second;
    }
    return res;
}
void solve(){
    cin>>n>>m;
    vector<int>a(n+1);
    map<int,int>mp;
    vector<int>mpp(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]-=i;
        mp[a[i]]++;
    }
    int idx=0;
    for(auto [pos,w]:mp){
        ++idx;
        mp[pos]=idx;
        mpp[idx]=pos;
    }
    int l=1,r=n;
    while(l<r){
        int mid=l+r+1>>1;
        build(1,1,idx+1);
        for(int i=1;i<mid;i++)modify(1,mp[a[i]],a[i],1);
        int flag=0;
//        cout<<mid<<endl;
        for(int i=mid;i<=n;i++){
            modify(1,mp[a[i]],a[i],1);
            int z=mpp[query(1,up(mid,2))];
//            cout<<i<<' '<<z<<endl;
            auto [lv,lcnt]=query(1,1,mp[z]);
            auto [rv,rcnt]=query(1,mp[z]+1,idx);
//            cout<<lcnt<<' '<<lv<<' '<<rcnt<<' '<<rv<<endl;
//            cout<<lcnt*z-lv+rv-rcnt*z<<' '<<m<<endl;
            if(lcnt*z-lv+rv-rcnt*z<=m)flag=1;
            modify(1,mp[a[i-mid+1]],-a[i-mid+1],-1);
        }
        if(flag)l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
}
signed main(){
    fast
    int t;t=1;cin>>t;
    while(t--) {
        solve();
    }
}