//音乐是苍白的鬼魂，就像玫瑰是疯狂而必死的美：她苍白而必死
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define vec vector
#define pb push_back
#define PDD pair<double,double>
#define PLL pair<ll,ll>
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define i128 __int128
#define ld long double
#define pi 3.1415926535
//const ll mod=1e9+7;
const ll mod=998244353;
bool isprime(ll x){
    if(x==1)return false;
    for(ll i=2;i<=x/i;i++){
        if(x%i==0)return false;
    }
    return true;
}
ll popcnt(ll x){
    ll cnt=0;
    while(x){
        if(x&1)cnt++;
        x>>=1;
    }
    return cnt;
}
ll qmi(ll a,ll b,ll p){
    if(a==0)return 1;
    a%=p;
    ll res=1;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
ll lowbit(ll x){return x&-x;}
const int N=1e6+10;
ll fact[N],infact[N];
ll C(ll n,ll m) {
    if (n < m || m < 0)return 0;
    return fact[n] * qmi(fact[m] * fact[n - m] % mod, mod - 2, mod) % mod;
}
//ll C(ll n,ll m){
//    if (n < m || m < 0)return 0;
//    return fact[n]%mod*infact[m]%mod*infact[n-m]%mod;
//}
//void scan(__int128 &x)
//{
//    x=0;int f=1;char ch=getchar();
//    while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
//    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
//    x*=f;
//}
//inline void print(__int128 x) {
//    if (x < 0) {
//        putchar('-');
//        x = -x;
//    }
//    if (x > 9) print(x / 10);
//}
//--------------------------------------------
int n,k,a[N];
bool check(int x){
    if(x==1)return 1;
    ll ans=1e18;
    ll sum1=0,sum2=0;
    multiset<int>st;
    st.insert(a[1]);
    sum1+=a[1];
    auto l=st.begin();
    auto r=st.begin();
    for(int i=2;i<=x;i++){
        st.insert(a[i]);
        if(st.size()%2==0){
            if(a[i]<*l)sum1+=(a[i]-*l),sum2+=*l,l--;
            else sum2+=a[i],r++;
        }
        else{
            if(a[i]<*l)sum1+=a[i],r--;
            else if(a[i]>=*l&&a[i]<*r)sum1+=a[i],l++,r--;
            else sum1+=*r,sum2+=(a[i]-*r),l++;
        }
    }
    for(int i=x+1;i<=n;i++){
        st.insert(a[i]);
        if(st.size()%2==0){
            if(a[i]<*l)sum1+=(a[i]-*l),sum2+=*l,l--;
            else sum2+=a[i],r++;
        }
        else{
            if(a[i]<*l)sum1+=a[i],r--;
            else if(a[i]>=*l&&a[i]<*r)sum1+=a[i],l++,r--;
            else sum1+=*r,sum2+=(a[i]-*r),l++;
        }
        int t=a[i-x];
        auto pos=st.lower_bound(t);
        if(pos==l){
            if(st.size()&1)sum1-=*l,l--,r++;
            else sum1-=*l,l++;
        }
        else if(pos==r)sum2-=*r,r--;
        else{
            int l1=*l,r1=*r;
            st.erase(pos);
            if(st.size()%2==0){
                if(t<l1)sum1-=t,r++;
                else if(t==l1)sum1-=t,l--,r++;
                else sum1-=l1,sum2+=(l1-t),l--;
            }
            else{
                if(t<l1)sum1+=(r1-t),sum2-=r1,l++;
                else if(t==l1&&t<r1)sum1+=(r1-t),sum2-=r1,l++;
                else sum2-=t,r--;
            }
        }
        if(st.size()&1){
            int mid=*l;
            ans=min(ans,mid*(n/2+1)-sum1+sum2-mid*(n/2));
        }
        else{
            int mid1=(*l+*r)/2;
            int mid2=mid1+1;
            ans=min(ans,mid1*(n/2)-sum1+sum2-mid1*(n/2));
            ans=min(ans,mid2*(n/2)-sum1+sum2-mid2*(n/2));
        }
    }
    if(st.size()&1){
        int mid=*l;
        ans=min(ans,mid*(n/2+1)-sum1+sum2-mid*(n/2));
    }
    else{
        int mid1=(*l+*r)/2;
        int mid2=mid1+1;
        ans=min(ans,mid1*(n/2)-sum1+sum2-mid1*(n/2));
        ans=min(ans,mid2*(n/2)-sum1+sum2-mid2*(n/2));
    }
    return ans<=k;
}
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i],a[i]-=(i-1);
    int l=1,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
}
int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T = 1;
    cin>>T;
    while (T--)solve();
    return 0;
}