#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<array>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void speed()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
inline ll read()
{
	ll x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch>'9')
	{
		if (ch == '-')
		{
			f = -1;
		}
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
		x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}

void solve()
{
	int n;
	ll k;
	//cin >> n >> k;
	auto ti = clock();
	n = read();
	k = read();
	vector<int>a(n + 1);
	for (int i = 1; i <= n; i++)
	{
		//cin >> a[i];
		a[i] = read();
		a[i] -= i;
	}

	int l = 1, r = n;
	int mid = 0;
	auto check = [&](int mid)
		{
			if (mid == 1)
				return 1;
			multiset<int>s1,s2;
			ll sum1 = 0;
			ll sum2 = 0;
			if (a[1] < a[2])
			{
				s1.insert(a[1]);
				s2.insert(a[2]);
				sum1 += a[1];
				sum2 += a[2];
			}
			else
			{
				s2.insert(a[1]);
				s1.insert(a[2]);
				sum2 += a[1];
				sum1 += a[2];
			}
			ll need = 1e15 + 1;
			if (mid == 2)
			{
				need = sum2 - sum1;
				if (*s1.begin() == a[1])
				{
					sum1 -= *s1.begin();
					s1.erase(s1.begin());
				}
				else
				{
					sum2 -= *s2.begin();
					s2.erase(s2.begin());
				}
			}
			for (int i = 3; i <= n; i++)
			{
				if (s2.empty()||a[i] >= *s2.begin())
				{
					s2.insert(a[i]);
					sum2 += a[i];
				}
				else
				{
					s1.insert(a[i]);
					sum1 += a[i];
				}
				while (!s1.empty()&&!s2.empty()&&*s1.rbegin() > *s2.begin())
				{
					s1.insert(*s2.begin());
					sum1 += *s2.begin();
					sum2 -= *s2.begin();
					s2.erase(s2.begin());
				}
				while (s2.size() > s1.size())
				{
					s1.insert(*s2.begin());
					sum1 += *s2.begin();
					sum2 -= *s2.begin();
					s2.erase(s2.begin());
				}
				while (s1.size() > s2.size()+1)
				{
					s2.insert(*s1.rbegin());
					sum1 -= *s1.rbegin();
					sum2 += *s1.rbegin();
					auto it = s1.end();
					it--;
					s1.erase(it);
				}
				if (i >= mid)
				{
					if (mid & 1)
					{
						need = min(need, sum2 - sum1 + *s1.rbegin());
					}
					else
					{
						need = min(need, sum2 - sum1);
					}
					auto pos1 = s1.lower_bound(a[i - mid + 1]);
					if (pos1 != s1.end())
					{
						sum1 -= a[i - mid + 1];
						s1.erase(pos1);
					}
					else
					{
						auto pos2 = s2.lower_bound(a[i - mid + 1]);
						sum2 -= a[i - mid + 1];
						s2.erase(pos2);
					}
				}
			}
			if (need <= k)
				return 1;
			else
				return 0;
		};
	while (l < r)
	{
		mid = (l + r + 1) >> 1;
		if (clock() - ti > 1000)
		{
			cout << 1 << endl;
			break;
		}
		if (check(mid))
		{
			l = mid;
		}
		else
		{
			r = mid - 1;
		}
	}
	cout <</*"ans:"<<*/ l << '\n';
}
int main()
{
	speed();
	int t;
	//cin >> t;
	t = read();
	while (t--)
	{
		solve();
	}
	return 0;
}