#pragma GCC optimize("Ofast")
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <cassert>
#include <random>
#include <chrono>
#include <ctime>
#include <cstdlib>
#define pii pair<int,int> 
#define mp make_pair
#define pb emplace_back
#define debug() cout<<"qwq"<<endl
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef unsigned long long ull;
const int DMAX = 500000 + 5;
const double INF = 1e9;
const int MOD = 998244353;
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
template<class T> inline void read(T &x){
    T f=1; x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1; 
        ch=getchar();
    }
    while(ch<='9' && ch>='0'){ x=x*10+ch-'0';ch=getchar(); }
    x*=f;
}
struct Fenwick{
    ll tr[DMAX];
    int n;
    void init(){
        for(int i = 1; i <= n; i++) tr[i] = 0;
    }
    int lowbit(int p){
        return p & (-p);
    }
    void add(int p, int v){
        for(int i = p; i <= n; i += lowbit(i)){
            tr[i] += v;
        }
    }
    ll ask(int p){
        ll res = 0;
        for(int i = p; i ; i -= lowbit(i)){
            res += tr[i];
        }
        return res;
    }
};
Fenwick bit1, bit2;
int T;
int n;
ll k;
ll a[DMAX], b[DMAX];
ll hve[DMAX];
multiset<int> s;
bool check(int v){
    s.clear();
    bit1.n = n, bit2.n = n;
    ll tot = 0;
    for(int i = 1; i <= n; i++) hve[i] = 0;
    bit1.init(), bit2.init();
    for(int i = 1; i <= v; i++){
        s.insert(a[i]);
        tot += b[a[i]];
        hve[a[i]] ++;
        bit1.add(a[i], 1);
        bit2.add(a[i], b[a[i]]);
    }
    int x = 0, temp = (v + 1) / 2;
    for(int i = 1; i <= v; i++){
        int val = bit1.ask(a[i] - 1);
        if(val < temp && val + hve[a[i]] >= temp){
            x = a[i];
            break;
        }
    }
    for(int i = v + 1; i <= n + 1; i++){
        ll sub0 = bit2.ask(x - 1);
        int hve0 = bit1.ask(x - 1);
        int hve1 = v - hve0;
        ll sub1 = tot - sub0;
        // cout<<i - 1<<":"<<endl;
        // cout<<b[x]<<endl;
        // cout<<hve0<<" "<<sub0<<" "<<hve1<<" "<<sub1<<endl;
        ll comp = sub1 - 1ll * b[x] * hve1 + 1ll * b[x] * hve0 - sub0;

        // cout<<i - v<<" "<<comp<<" "<<b[x]<<endl;
        // cout<<i - 1<<" "<<comp<<endl;
        if(comp <= k){
            return 1;
        } 
        if(i == n + 1) break;

        auto it = s.find(a[i - v]);
        hve[a[i - v]] --, tot -= b[a[i - v]];
        bit1.add(a[i - v], -1), bit2.add(a[i - v], -b[a[i - v]]);
        s.erase(it);

        s.insert(a[i]);
        hve[a[i]]++, tot += b[a[i]];
        // bit1.add(a[i], 1), bit2.add(a[i], b[a[i]]);
        // if(i == n){
        //     cout<<i<<":"<<endl;
        //     for(auto v:s){
        //         cout<<b[v]<<" ";
        //     }
        //     cout<<endl;
        // }
        it = s.find(x);
        if(it == s.end()){
            it = s.upper_bound(x);
            if(it != s.begin()){
                it --;
            }
        }
        int pol = x;
        int val;
        if(it != s.begin()){
            val = bit1.ask(*it - 1);
            if(val < temp && val + hve[*it] >= temp){
                pol = *it;
            } 
        }
        val = bit1.ask(x - 1);
        if(val < temp && val + hve[x] >= temp){
            pol = x;
        }
        auto it2 = s.upper_bound(x);
        if(it2 != s.end()){
            val = bit1.ask(*it2 - 1);
            if(val < temp && val + hve[*it2] >= temp){
                pol = *it2;
            }
        }
        if(it != s.begin()){
            it --;
            val = bit1.ask(*it - 1);
            if(val < temp && val + hve[*it] >= temp){
                pol = *it;
            } 
        }
        x = pol;
    }
    return 0;
}
void solve(){
    read(n), read(k);
    for(int i = 1; i <= n; i++){
        read(a[i]);
        a[i] -= i;
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int len = unique(b + 1, b + n + 1) - b - 1;
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
    }

    int l = 2, r = n + 1, res = 1;
    // cout<<check(3)<<endl;
    // return ;
    while(l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            res = mid, l = mid + 1;
        }
        else r = mid;
    }
    printf("%d\n", res);
    return ;
}
int main(){
    read(T);
    while(T--){
        solve();
    }
    return 0;
}