#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
#define int long long
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mxn=5e5+5;
int a[mxn];
int n;
int check(int x)
{
	static int b[mxn];
	int i,j,s1=0,s2=0,ans,mid;
	multiset<int> mn,mx;
	for(i=1;i<=x;i++)
		b[i]=a[i];
	sort(b+1,b+1+x);
	for(i=1;i<=x/2;i++)
		mn.insert(b[i]),s1+=b[i];
	for(;i<=x;i++)
		mx.insert(b[i]),s2+=b[i];
	mid=*mx.begin();
	ans=mid*(int)mn.size()-s1+s2-(int)mx.size()*mid;
	for(;i<=n;i++)
	{
		if(a[i]<=*mn.end()) mn.insert(a[i]),s1+=a[i];
		else mx.insert(a[i]),s2+=a[i];
		if(mn.find(a[i-x])!=mn.end()) mn.erase(mn.find(a[i-x])),s1-=a[i-x];
		else mx.erase(mx.find(a[i-x])),s2-=a[i-x];
		while(mn.size()<x/2) s1+=*mx.begin(),s2-=*mx.begin(),mn.insert(*mx.begin()),mx.erase(mx.begin());
		while(mn.size()>x/2) s1-=*mn.begin(),s2+=*mn.begin(),mx.insert(*mn.begin()),mn.erase(mn.begin());	
		mid=*mx.begin();
		ans=min(ans,mid*(int)mn.size()-s1+s2-(int)mx.size()*mid);
	}
	return ans;
}
signed main()
{
	int T=read();
	while(T--)
	{
		n=read();
		int k=read(),i,w=1;
		for(i=1;i<=n;i++)
			a[i]=read()-i;
		for(i=1<<20;i;i>>=1)
			w+=(w+i<=n&&check(w+i)<=k)*i;
		printf("%d\n",w);
	}
}
/*
1
5 50
100 200 300 400 500

*/