//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define N 500005
#define mod 998244353
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define fi first
#define se second
#define INF 1e9
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
	}
	return res;
}
/*int fac[N],ifac[N];
int C(int n,int m){
	if(m>n||m<0||n<0) return 0;
	return fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
void init(){
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
	ifac[N-1]=qpow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}*/
inline int lowbit(int x){return x&(-x);}
inline int read(){
  int x=0,t=1;char ch=getchar();
  while(ch<'0'||ch>'9'){
    if(ch=='-') t=-1;
    ch=getchar();
  }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return x*t;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int T,n,a[N],K,b[N],sum1,sum2,tmp,pre;
multiset<int>s1;
multiset<int>s2;
int getval(){
	int pos=(*prev(s1.end()));
	int res=pre*pos-sum1+sum2-(tmp-pre)*pos;
	return res;
}
int check(int lim){
	s1.clear();s2.clear();tmp=lim;
	pre=(lim+1)/2;sum1=0,sum2=0;
	for(int i=1;i<=lim;i++)
		b[i]=a[i];
	sort(b+1,b+lim+1);int ans=INF*INF;
	for(int i=1;i<=pre;i++) sum1+=b[i],s1.insert(b[i]);
	for(int i=pre+1;i<=lim;i++) sum2+=b[i],s2.insert(b[i]);
	ans=min(ans,getval());
	for(int i=lim+1;i<=n;i++){
		int x=a[i-lim];
		auto it=s1.find(x);
		if(it!=s1.end()){
			s1.erase(it);sum1-=x;
			int t=(*s2.begin());sum2-=t;
			s2.erase(s2.begin());sum1+=t;s1.insert(t);
		}else{
			it=s2.find(x);
			s2.erase(it);sum2-=x;
		}
		int tmp=(*prev(s1.end()));
		if(a[i]>=tmp) s2.insert(a[i]),sum2+=a[i];
		else{
			s1.erase(prev(s1.end()));sum1-=tmp;
			s2.insert(tmp);s1.insert(a[i]);sum1+=a[i];sum2+=tmp;
		}
		/*
		cout<<getval()<<endl;
		for(auto t:s1) cout<<t<<" ";
		cout<<endl;
		for(auto t:s2) cout<<t<<" ";
		cout<<endl;*/
		ans=min(ans,getval());
	}
	if(ans<=K) return 1;
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		//0 2 1 -1
		cin>>n>>K;
		for(int i=1;i<=n;i++) cin>>a[i],a[i]-=i;
		int l=2,r=n,ans=1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(check(mid)) ans=mid,l=mid+1;
			else r=mid-1;
		}
		cout<<ans<<endl;
	}
	return 0;
}