#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef long long ll;
#define re read()
#define INF 2147483640
#define fr(i, x, y) for (int i = x, _ = y; i <= _; ++i)
#define rp(i, x, y) for (int i = x, _ = y; i >= _; --i)
#define Timeok ((double)clock() / CLOCKS_PER_SEC < MAX_TIME)
const double MAX_TIME = 1.0 - 0.0032;

inline ll read()
{
    ll x = 0, f = 0;
    char ch = getchar();
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^= 48), ch = getchar();
    return f ? -x : x;
}

void write(ll x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + 48);
}

inline void W(ll x, char ch)
{
    write(x);
    putchar(ch);
}

/*------------C-O-D-E------------*/

const int N = 5e5 + 32;
ll n, m, k;
int a[N];
multiset<int> s1;
multiset<int> s2;
ll sum1, sum2;

void Change()
{
    while(s1.size() > s2.size() + 1)
    {
        ll x = *(--s1.end());
        s1.erase(--s1.end());
        s2.insert(x);
        sum1 -= x;
        sum2 += x;
    }
    while(s2.size() > s1.size())
    {
        ll x = *s2.begin();
        s2.erase(s2.begin());
        s1.insert(x);
        sum2 -= x;
        sum1 += x;
    }
}

void Insert(int x)
{
    if(x <= *s2.begin()) 
    {
        s1.insert(x);
        sum1 += x;
    }
    else
    {
        s2.insert(x);
        sum2 += x;
    }
    Change();
}

void Del(int x)
{
    auto it = s1.lower_bound(x);
    if(it != s1.end())
    {
        sum1 -= *it;
        s1.erase(it);
    }
    else
    {
        it = s2.lower_bound(x);
        sum2 -= *it;
        s2.erase(it);
    }
    Change();
}

int Zhong()
{
    return *s1.rbegin();
}

ll Calc()
{
    ll zh = Zhong();
    ll ans = 0;
    ans += sum2 - ((1LL * s2.size()) * zh);
    ans += ((1LL * s1.size()) * zh) - sum1;
    return ans;
}

bool Check(ll x)
{
    s1.clear();
    s2.clear();
    s1.insert(-INF);
    s2.insert(INF);
    sum1 = 0;
    sum2 = 0;

    fr(i, 1, x)
    {
        // Insert(a[i]);
        s1.insert(a[i]);
        sum1 += a[i];
    }
    Change();
    if(Calc() <= m) return 1;
    // W(Calc(), '\n');

    fr(i, x+1, n)
    {
        Insert(a[i]);
        Del(a[i-x]);
        if(Calc() <= m) return 1;
        // W(Calc(), '\n');
    }
    return 0;
}


int main()
{
    // cin.tie(0);
    // cout.tie(0);
    // ios::sync_with_stdio(false);
    // ll T = re;
    ll T;
    T = re;
    while (T--)
    {
        n = re, m = re;
        fr(i, 1, n)
        {
            a[i] = re;
            a[i] -= i;
        }

        int l = 0, r = min(n, 1LL * 172999);
        // Check(4);
        while (l < r)
        {
            int mid = (l + r) / 2 + 1;
            if (Check(mid))
                l = mid; 
            else
                r = mid - 1;
        }
        W(l, '\n');

        // fr(i, 1, n) a[i] = 0;
    }
    return 0;
}