#include <bits/stdc++.h>
#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());


void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n+1);
    vector<int> nums;
    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());

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

    vector<int> BIT(nums.size() + 1), cBIT(nums.size() + 1);

    auto add = [&](int x, int val, int c)->void{
        for(int i = x; i <= nums.size(); i += i&-i){
            BIT[i] += val, cBIT[i] += c;
        }
    };

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

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

    auto cal = [&](int l)->int{
        int res = INF;

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

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

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

                int l_c = cqry(find(avg));
                int r_c = cqry(nums.size()) - l_c;
                int l_sum = qry(find(avg));
                int r_sum = qry(nums.size()) - 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);
        }

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

        return res;
    };

    int i = 1;
    for(int j = n-1; j > 0; j /= 2){
        while(i + j <= n && cal(i + j) <= k) i += j;
    }

    cout << i << '\n';
}

int32_t main(){
    int tt;
    cin >> tt;

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

// 7 2 5 5 4 11 7
// 1 2 3 4 5 6 7
// 6 0 2 1 1 5 0
// 6 0 2 1 -1 5 0