#include <bits/stdc++.h>

using namespace std;

#define int long long
#define deg( x ) cout<<""#x"="<<x<<endl
#define endl '\n'
#define pll pair<int,int>
#define fr first
#define se second

const int N=5e5+10;
const int mod=1e9+7;

int A[ N ];

int chack( int len , int mid , int n ){
    int re=1e18;

    int ma=0 , mi=0;
    int masum=0 , misum=0;

    for( int i=1; i<=len; i++ ){
        if( A[ i ]<mid ){
            mi++; misum+=A[ i ];
        }
        else if( A[ i ]>mid ){
            ma++; masum+=A[ i ];
        }
    }

    re=min( re , ( masum-ma*mid + mi*mid-misum ) );

    int r=len;
    for( int l=1; r<=n; l++,r++ ){
        re=min( re , ( masum-ma*mid + mi*mid-misum ) );
        if( A[ l ]<mid ){
            mi--; misum-=A[ l ];
        }
        if( A[ l ]>mid ){
            ma--; masum-=A[ l ];
        }

        if( A[ r+1 ]<mid ){
            mi++; misum+=A[ r+1 ];
        }
        if( A[ r+1 ]>mid ){
            ma++; masum+=A[ r+1 ];
        }
    }

    return re;
}

bool check( int len , int n , int k ){
    int l=-1e5 , r=1e10;

    while( r-l+1 >= 4 ){ // 至少能分出 l+1 , l+2
        int mid=( r-l+1 )/3;
        int ll=l+mid , rr=l+2*mid; // 分出两个点
        int tell=chack( len , ll , n ) , terr=chack( len , rr , n ); // 点的权值

        if( tell < terr ) r=rr;
        else l=ll;
    }

    int re=1e18;
    for( int i=l; i<=r; i++ ){ // 最后三个点单独取最小值
        re=min( re , chack( len , i , n ) );
        //deg( i );
    }

    //deg( re );

    return re<=k;
}

void solve(  ){
    int n,k;
    cin>>n>>k;

    for( int i=1; i<=n; i++ ){
        cin>>A[ i ];
        A[ i ]-=i;
    }

    int l=1,r=n;
    while( l<=r ){
        int mid=l+r>>1;
        if( check( mid , n , k ) ) l=mid+1;
        else r=mid-1;
    }

    l--;
    cout<<l<<endl;

}

signed main() {
    ios::sync_with_stdio( 0 );
    cin.tie( 0 ); cout.tie( 0 );

    int T=1;
    cin>>T;

    while( T-- ){
        solve(  );
    }

    return 0;
}