/*[[
 ⣇⣿⠘⣿⣿⣿⡿⡿⣟⣟⢟⢟⢝⠵⡝⣿⡿⢂⣼⣿⣷⣌⠩⡫⡻⣝⠹⢿⣿⣷ ]],[[
 ⡆⣿⣆⠱⣝⡵⣝⢅⠙⣿⢕⢕⢕⢕⢝⣥⢒⠅⣿⣿⣿⡿⣳⣌⠪⡪⣡⢑⢝⣇ ]],[[
 ⡆⣿⣿⣦⠹⣳⣳⣕⢅⠈⢗⢕⢕⢕⢕⢕⢈⢆⠟⠋⠉⠁⠉⠉⠁⠈⠼⢐⢕⢽ ]],[[
 ⡗⢰⣶⣶⣦⣝⢝⢕⢕⠅⡆⢕⢕⢕⢕⢕⣴⠏⣠⡶⠛⡉⡉⡛⢶⣦⡀⠐⣕⢕ ]],[[
 ⡝⡄⢻⢟⣿⣿⣷⣕⣕⣅⣿⣔⣕⣵⣵⣿⣿⢠⣿⢠⣮⡈⣌⠨⠅⠹⣷⡀⢱⢕ ]],[[
 ⡝⡵⠟⠈⢀⣀⣀⡀⠉⢿⣿⣿⣿⣿⣿⣿⣿⣼⣿⢈⡋⠴⢿⡟⣡⡇⣿⡇⡀⢕ ]],[[
 ⡝⠁⣠⣾⠟⡉⡉⡉⠻⣦⣻⣿⣿⣿⣿⣿⣿⣿⣿⣧⠸⣿⣦⣥⣿⡇⡿⣰⢗⢄ ]],[[
 ⠁⢰⣿⡏⣴⣌⠈⣌⠡⠈⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣬⣉⣉⣁⣄⢖⢕⢕⢕ ]],[[
 ⡀⢻⣿⡇⢙⠁⠴⢿⡟⣡⡆⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣵⣵⣿ ]],[[
 ⡻⣄⣻⣿⣌⠘⢿⣷⣥⣿⠇⣿⣿⣿⣿⣿⣿⠛⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿ ]],[[
 ⣷⢄⠻⣿⣟⠿⠦⠍⠉⣡⣾⣿⣿⣿⣿⣿⣿⢸⣿⣦⠙⣿⣿⣿⣿⣿⣿⣿⣿⠟ ]],[[
 ⡕⡑⣑⣈⣻⢗⢟⢞⢝⣻⣿⣿⣿⣿⣿⣿⣿⠸⣿⠿⠃⣿⣿⣿⣿⣿⣿⡿⠁⣠ ]],[[
 ⡝⡵⡈⢟⢕⢕⢕⢕⣵⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣶⣿⣿⣿⣿⣿⠿⠋⣀⣈⠙ ]],[[
 ⡝⡵⡕⡀⠑⠳⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⢉⡠⡲⡫⡪⡪⡣ ]],*/
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define int long long
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=1e6+10;
ll n,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;
	map<ll,int>mp;
//	cout<<x<<endl;
	ll ans=1e18;
	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++;
			fu.insert(w);
		}
		if(w>base){
			lenzh++,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)zh.erase(zh.find(tw));
			}
			if(tw<base){
				lenfu--;
				if(mp[tw]==0)fu.erase(fu.find(tw));
			}
			if(tw==base)basex--;
		}
		
		while(lenzh>basex+lenfu){
			if(zh.size()==0)break;
			tt++;
			if(tt>=5*n){
				return false;
			}
			ll w=abs(*zh.begin()-base);
			res-=w*abs(basex+lenfu-lenzh);
		//	cout<<w*abs(basex+lenfu-lenzh)<<endl;
			fu.insert(base);w=*zh.begin();
			lenfu+=basex;
			basex=mp[w];
			base=w;
			lenzh-=mp[w];
			zh.erase(zh.begin());
		}
		while(lenfu>basex+lenzh){
			if(fu.size()==0)break;
			tt++;
			if(tt>=5*n){
				return false;
			}
			ll w=abs(*--fu.end()-base);
			res-=w*abs(basex+lenzh-lenfu);
			//	cout<<w*abs(basex+lenzh-lenfu)<<endl;
			zh.insert(base);
			w=*--fu.end();
			lenzh+=basex;
			basex=mp[w];
			base=w;
			lenfu-=mp[w];
			fu.erase(--fu.end());
		}
		if(i>=x)ans=min(ans,res);
	//	cout<<res<<" s "<<base<<" b "<<i<<endl;
	}
	if(ans<=k)return true;
	return false;
}
void solve(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	ll l=1,r=n;
	ll tt=0;
	while(l<r){
		tt++;
		if(tt>=10&&tt>=100)break;
		ll mid=(l+r+1)>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}
	cout<<l<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int _=1;
	cin>>_;
	while(_--)solve();
	return 0;
}