#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
#define int LL
// #define BOOL 	
const int N = 5e5 + 5;
int a[N];

#ifdef BOOL
bool solve()
#else
void solve()
#endif
{
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] -= i;
    auto check = [&](int x) -> bool
    {
        LL ans = 1e18;
        multiset<int> less;
        multiset<int, greater<int>> more;
        int now = 0;
        int last = -1, cntless = 0, cntmore = 0;
        for(int i = 1, j = i; j <= n; j++)
        {
            if(j - i + 1 > x)
            {
                if(more.find(a[i]) != more.end()) more.erase(more.find(a[i]));
                else if(less.find(a[i]) != less.end()) less.erase(less.find(a[i]));
                now -= abs(a[i] - last);
                i++;
                if(more.size() > less.size() + 1)
                {
                    int t = *more.begin();
                    more.erase(more.begin());
                    less.insert(t);
                }
                
                if(less.size() > more.size())
                {
                    int t = *less.begin();
                    less.erase(less.begin());
                    more.insert(t);
                }
            }

            if(more.empty() || a[j] <= *more.begin())
                more.insert(a[j]);
            else
                less.insert(a[j]);

            if(more.size() > less.size() + 1)
            {
                int t = *more.begin();
                more.erase(more.begin());
                less.insert(t);
            }
            
            if(less.size() > more.size())
            {
                int t = *less.begin();
                less.erase(less.begin());
                more.insert(t);
            }

            int mid = *more.begin();
            if(last != -1)
            {
                if(mid > last)
                {
                    now += (mid - last) * cntless;
                    now -= (mid - last) * cntmore;
                }
                else if(mid < last)
                {
                    now -= (mid - last) * cntless;
                    now += (mid - last) * cntmore;
                }
            }
            now += abs(a[j] - mid);
            last = mid;
            cntless = more.size();
            cntmore = less.size();
            if(j >= x) ans = min(ans, now);
        }
        return ans <= k;
    };

    int l = 1, r = n;
    while(l < r)
    {
        int 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(nullptr);
	int t = 1;
	cin >> t;
	while (t--)
	{
		#ifdef BOOL
		if(solve()) cout << "Yes\n";
		else cout << "No\n";
		#else
		solve();
		#endif
	}
	return 0;
}