#include <bits/stdc++.h>
using i64 = long long;

template<typename T>
struct Fenwick {
    Fenwick(int n) : v(n + 1) {}
    void update(int pos, T dx) {
        for(int i = pos; i < v.size(); i += (i & -i)) {
            v[i] += dx;
        }
    }
    T query(int pos) {
        T res{};
        for(int i = pos; i > 0; i -= (i & -i)) {
            res += v[i];
        }
        return res;
    }
    T range(int l, int r) {
        return query(r) - query(l - 1);
    }
    std::vector<T> v;
};

void solve() {
    i64 n, k;
    std::cin >> n >> k;
    std::vector<i64> v(n + 1), pre(n + 1);
    for(int i = 1; i <= n; ++i) {
        std::cin >> v[i];
        v[i] = v[i] - i + n;
        pre[i] = pre[i - 1] + v[i];
    }
    std::vector<i64> temp = v;
    std::sort(temp.begin() + 1, temp.end());
    temp.erase(std::unique(temp.begin() + 1, temp.end()), temp.end());
    std::vector<int> pos(n + 1);
    for(int i = 1; i <= n; ++i) {
        pos[i] = std::lower_bound(temp.begin() + 1, temp.end(), v[i]) - temp.begin();
    }

    Fenwick<i64> tr(n);
    Fenwick<i64> tot(n);
    std::multiset<i64> st1, st2;
    auto modify = [&](i64 p, i64 sgn) ->void {
        tr.update(pos[p], 1LL * sgn * v[p]);
        tot.update(pos[p], sgn);
    };
    auto balance = [&](int k) ->void {
        while(st1.size() > k) {
            i64 val = *st1.rbegin();
            st1.extract(val);
            st2.insert(val);
        }
        while(st1.size() < k && st2.size()) {
            i64 val = *st2.begin();
            st1.insert(val);
            st2.extract(val);
        }
    };
    auto insert = [&](i64 val) ->void {
        st1.insert(val);
    };
    auto erase = [&](i64 val) ->void {
        if(st1.find(val) != st1.end()) {
            st1.extract(val);
        } else {
            st2.extract(val);
        }
    };
    i64 l = 1, r = n, ans = 1;
    while(l <= r) {
        i64 mid = (l + r) / 2;
        i64 res = LLONG_MAX;
        i64 i = 1, j = 1;
        while(j < mid) {
            modify(j, 1);
            insert(v[j]);
            balance((mid + 1) / 2);
            ++j;
        }
        while(j <= n) {
            modify(j, 1);
            insert(v[j]);
            balance((mid + 1) / 2);

            //i64 ave = std::round((double)(pre[j] - pre[i - 1]) / mid);
            i64 ave = *st1.rbegin();

            i64 p = std::upper_bound(temp.begin() + 1, temp.end(), ave) - temp.begin() - 1;
            i64 num = tot.range(1, p);
            i64 sum = 1LL * ave * num - tr.range(1, p) + tr.range(p + 1, n) - 1LL * ave * (mid - num); 
            res = std::min(res, sum);
            modify(i, -1);
            erase(v[i]);
            balance((mid + 1) / 2);
            ++i, ++j;
        }
        while(i <= n) {
            modify(i, -1);
            erase(v[i]);
            ++i;
        }
        if(res <= k) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    std::cout << ans << '\n';
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while(T--) {
        solve();
    }
}