#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(2)
#pragma G++ optimize(3)

#define int long long
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

int INF = 1e18; 
const int MOD = 998244353;
const int N = 5e5 + 10;
const int LOG = 20;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int BIT[N], cBIT[N], a[N];
int sz;

void add(int x, int val, int c){
    for(int i = x; i < sz; i += i&-i){
        BIT[i] += val, cBIT[i] += c;
    }
}

int qry(int x){
    int res = 0;
    for(int i = x; i > 0; i -= i&-i) res += BIT[i];
    return res;
}
    
int cqry(int x){
    int res = 0;
    for(int i = x; i > 0; i -= i&-i) res += cBIT[i];
    return res;
}

vector<int> nums;
int n, k;

int find(int x){
    int res = lower_bound(all(nums), x) - nums.begin();
    if(nums[res] == x) res++;
    return res;
}

int cal(int l){
    int res = INF, tot = 0;

    for(int i = 1; i <= l-1; i++){
        add(find(a[i]), a[i], 1);
        tot += a[i];
    }

    for(int i = l; i <= n; i++){
        add(find(a[i]), a[i], 1);
        tot += a[i];

        int avg = qry(nums.size()) / l;
        for(int j = -1; j <= 1; j++){
            avg += j;

            int l_c = cqry(find(avg));
            int r_c = l - l_c;
            int l_sum = qry(find(avg));
            int r_sum = tot - l_sum;
                
            res = min(res, l_c * avg - l_sum + r_sum - r_c * avg);

            avg -= j;
        }

        add(find(a[i - l + 1]), -a[i - l + 1], -1);
        tot -= a[i - l + 1];
    }

    for(int i = n - l + 2; i <= n; i++) add(find(a[i]), -a[i], -1);

    return res;
};

void solve(){
    cin >> n >> k;    
    nums.clear();
    nums.push_back(0);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] -= i;
        if(a[i] < 0) a[i] = -a[i];
        nums.push_back(a[i]);
    }

    sort(all(nums));
    nums.erase(unique(all(nums)), nums.end());
    sz = nums.size();

    int l = 1, r = n;
    while(l < r){
        int mid = (l+r)/2;
        if(cal(mid) <= k) l = mid+1;
        else r = mid-1;
    }
    if(cal(l) > k) l--;

    cout << l << '\n';
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int tt;
    cin >> tt;

    while(tt--){
        solve();
    }
}