///////////        
//                   //      //
//              ////////////////////
//                   //      //
//                 
///////////

//          
//          
//           //     //    ////////     /\     /////////
//           //     //   //      //          //       //
//            ////////   //      //    //    //       //
//                  //   //      //    //    //       //
//////////   ////////    //      //    //     /////////////

#pragma GCC optimize(2)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>

using namespace std;

#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define endl '\n'
#define px first
#define py second
#define DEBUG(a) cout<<a<<endl

using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
	out << '(' << p.first << ", " << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
	for (T i : ve)
		out << i << ' ';
	return out;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
	for (auto i : mp)
		out << i << '\n';
	return out;
}

const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

//#include "Lynia.h"

const int mod = 998244353;
const int N = 1e6 + 10;

void solve(int CASE)
{
	ll n, k; cin >> n >> k;
	var a = vector<ll>(n + 1, 0);
	fa(i, 1, n)cin >> a[i], a[i] -= i;

	var check = [&](ll mid)->bool {
		multiset<ll>r;
		multiset<ll, greater<ll>>l;
		ll l_sum = 0, r_sum = 0;

		var f = [&]()->void {
			while (l.size() and (*l.begin()) > (*r.begin())) {
				r_sum += (*l.begin()), r.insert((*l.begin()));
				l_sum -= (*l.begin()), l.erase(l.begin());
			}
			if (mid & 1) {
				while (l.size() < r.size() + 1) {
					l_sum += (*r.begin()), l.insert(*r.begin());
					r_sum -= (*r.begin()), r.erase(r.begin());
				}
				while (l.size() > r.size() + 1) {
					r_sum += (*l.begin()), r.insert(*l.begin());
					l_sum -= (*l.begin()), l.erase(l.begin());
				}
			}
			else {
				while (l.size() < r.size()) {
					l_sum += (*r.begin()), l.insert(*r.begin());
					r_sum -= (*r.begin()), r.erase(r.begin());
				}
				while (l.size() > r.size()) {
					r_sum += (*l.begin()), r.insert(*l.begin());
					l_sum -= (*l.begin()), l.erase(l.begin());
				}
			}
			};

		ll mn = LINF;
		fa(i, 1, mid) {
			if (l.size() == 0)l_sum += a[i], l.insert(a[i]);
			else {
				if (a[i] <= (*l.begin()))l_sum += a[i], l.insert(a[i]);
				else r_sum += a[i], r.insert(a[i]);
			}
		}

		f(); // 刷新双set
		ll mmid = (*l.begin()); // 中位数
		mn = min(mn, (mmid * (ll)l.size() - l_sum) + (r_sum - mmid * (ll)r.size()));
		ll ffff = 0;
		if (CASE == 11002 and l.size() - r.size() != 1) {
			ffff = max(ffff, (ll)(l.size() - r.size()));
		}
		fa(i, mid + 1, n) {
			if (l.count(a[i - mid])) l_sum -= a[i - mid], l.erase(a[i - mid]);
			else r_sum -= a[i - mid], r.erase(a[i - mid]);

			if (a[i] <= (*l.begin()))l_sum += a[i], l.insert(a[i]);
			else r_sum += a[i], r.insert(a[i]);

			f(); // 刷新双set
			mmid = (*l.begin()); // 中位数
			mn = min(mn, (mmid * (ll)l.size() - l_sum) + (r_sum - mmid * (ll)r.size()));
			if (CASE == 11002 and l.size() - r.size() != 1) {
				ffff = max(ffff, (ll)(l.size() - r.size()));
			}
		}

		if (CASE == 11002) {
			if (ffff == 1)cout << l.size() << endl;
			else cout << 0 << endl;
		}

		return mn <= k;
		};

	if (CASE == 11002) {
		check(517);
		return;
	}
	ll l = 1, r = n;
	while (l < r) {
		ll mid = l + r + 1 >> 1;
		if (check(mid))l = mid;
		else r = mid - 1;
	}
	cout << l << endl;
	return;
}

int main()
{
	//SetConsoleOutputCP(CP_UTF8);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	fa(i, 1, _)solve(i);
	return 0;
}