/*[[
 ⣇⣿⠘⣿⣿⣿⡿⡿⣟⣟⢟⢟⢝⠵⡝⣿⡿⢂⣼⣿⣷⣌⠩⡫⡻⣝⠹⢿⣿⣷ ]],[[
 ⡆⣿⣆⠱⣝⡵⣝⢅⠙⣿⢕⢕⢕⢕⢝⣥⢒⠅⣿⣿⣿⡿⣳⣌⠪⡪⣡⢑⢝⣇ ]],[[
 ⡆⣿⣿⣦⠹⣳⣳⣕⢅⠈⢗⢕⢕⢕⢕⢕⢈⢆⠟⠋⠉⠁⠉⠉⠁⠈⠼⢐⢕⢽ ]],[[
 ⡗⢰⣶⣶⣦⣝⢝⢕⢕⠅⡆⢕⢕⢕⢕⢕⣴⠏⣠⡶⠛⡉⡉⡛⢶⣦⡀⠐⣕⢕ ]],[[
 ⡝⡄⢻⢟⣿⣿⣷⣕⣕⣅⣿⣔⣕⣵⣵⣿⣿⢠⣿⢠⣮⡈⣌⠨⠅⠹⣷⡀⢱⢕ ]],[[
 ⡝⡵⠟⠈⢀⣀⣀⡀⠉⢿⣿⣿⣿⣿⣿⣿⣿⣼⣿⢈⡋⠴⢿⡟⣡⡇⣿⡇⡀⢕ ]],[[
 ⡝⠁⣠⣾⠟⡉⡉⡉⠻⣦⣻⣿⣿⣿⣿⣿⣿⣿⣿⣧⠸⣿⣦⣥⣿⡇⡿⣰⢗⢄ ]],[[
 ⠁⢰⣿⡏⣴⣌⠈⣌⠡⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣬⣉⣉⣁⣄⢖⢕⢕⢕ ]],[[
 ⡀⢻⣿⡇⢙⠁⠴⢿⡟⣡⡆⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣵⣵⣿ ]],[[
 ⡻⣄⣻⣿⣌⠘⢿⣷⣥⣿⠇⣿⣿⣿⣿⣿⣿⠛⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ]],[[
 ⣷⢄⠻⣿⣟⠿⠦⠍⠉⣡⣾⣿⣿⣿⣿⣿⣿⢸⣿⣦⠙⣿⣿⣿⣿⣿⣿⣿⣿⠟ ]],[[
 ⡕⡑⣑⣈⣻⢗⢟⢞⢝⣻⣿⣿⣿⣿⣿⣿⣿⠸⣿⠿⠃⣿⣿⣿⣿⣿⣿⡿⠁⣠ ]],[[
 ⡝⡵⡈⢟⢕⢕⢕⢕⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣿⣿⣿⣿⣿⠿⠋⣀⣈⠙ ]],[[
 ⡝⡵⡕⡀⠑⠳⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢉⡠⡲⡫⡪⡪⡣ ]],*/
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
using ll =long long ;
using pii =pair<int,int>;
using pll=pair<ll,ll>;
using pcc=pair<char,char>;
bool cmp(pll a,pll b){
	return a.y<b.y;
}
struct cmp1{
    bool operator()(pair<ll,ll>a,pair<ll,ll>b){
	if(a.x==b.x)return a.y>b.y;
	return a.x>b.x; 
}
};
const int mod=998244353;
ll ksm(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1){
			ans*=a;
		ans=ans%mod;
		}
		a=a*a;a%=mod;
		b>>=1;
	}
	return ans;
}
ll gcd(ll a,ll b){
	ll t=a%b;
	while(t){
		a=b;
		b=t;
		t=a%b;
	}
	return b;
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
ll get_inv(ll x){
	return ksm(x,mod-2);
}
const int N=6e5+10;
int n;
ll k;
ll a[N];
/* 
5
7 5
7 2 5 5 4 11 7
6 0
100 3 4 5 99 100
5 6
1 1 1 1 1
5 50
100 200 300 400 500
1 100
3
*/
bool check(ll x){
	if(x==1)return true;
	unordered_map<ll,int>mp;
//	cout<<x<<endl;
	ll ans=1e16;
	set<ll>zh,fu;
	ll res=0;
	int lenzh=0,lenfu=0;
	ll base=0,basex=0;ll tt=0;
	for(int i=1;i<=n;++i){
		ll w=a[i]-i;
		if(w==base)++basex;
		++mp[w];
		if(w<base){
			++lenfu;
			if(mp[w]==1)fu.insert(w);
		}
		if(w>base){
			++lenzh;
			if(mp[w]==1)zh.insert(w);
		}
		res+=abs(w-base);
		if(i>x){
			ll tw=a[i-x]-(i-x);
			--mp[tw];
			res-=abs(tw-base);
			if(tw>base){
				lenzh--;
				if(mp[tw]==0){
				auto t=zh.find(tw);
				zh.erase(t);
				}
			}
			if(tw<base){
				lenfu--;
				if(mp[tw]==0){
				auto t=fu.find(tw);
				fu.erase(t);
				}
			}
			if(tw==base)--basex;
		}
		
		while(lenzh>basex+lenfu){
			tt++;if(tt>=5*n){
				break;
			}
			if(zh.size()==0)break;
			auto t=zh.begin();
			ll w=abs(*t-base);
			res-=w*abs(basex+lenfu-lenzh);
		//	cout<<w*abs(basex+lenfu-lenzh)<<endl;
			fu.insert(base);w=*t;
			lenfu+=basex;int mpw=mp[w];
			basex=mpw;
			base=w;
			lenzh-=mpw;
			zh.erase(t);
		}
		while(lenfu>basex+lenzh){
			tt++;
			
			if(tt>=5*n){
				break;
			}
			if(fu.size()==0)break;
			auto t=--fu.end();
			ll w=abs((*t)-base);
			res-=w*abs(basex+lenzh-lenfu);
			zh.insert(base);
			w=*t;int mpw=mp[w];
			lenzh+=basex;
			basex=mpw;
			base=w;
			lenfu-=mpw;
			fu.erase(t);
		}
		if(i>=x)ans=min(ans,res);
	if(ans<=k)return true;
	}
	
	return false;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	int l=1,r=n;
	int t=0;
	while(l<r){
		t++;
		if(t>=50)break;
		int mid=(l+r+1)>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	cout<<l<<'\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cout.tie(0);
	int _=1;
	cin>>_;
	while(_--)solve();
	return 0;
}