#include <bits/stdc++.h>

using namespace std;

const int MaxN = 1e5 + 15;

int n, S;
pair<int, int> a[MaxN];
int ans[MaxN];

struct segmetTree{
    vector <int> t;
    int n;

    segmetTree(int n) :n(n)
    {
        t.resize(n * 4);
    }

    void up(int x, int l, int r, int pos, int newV)
    {
        if(l == r)
            t[x] = newV;
        else
        {
            int mid = (l + r) / 2;
            if(mid >= pos)
                up(x + x, l, mid, pos, newV);
            else
                up(x + x + 1, mid + 1, r, pos, newV);

            t[x] = max(t[x + x], t[x + x + 1]);
        }
    }
    void up(int pos, int newV)
    {
        up(1, 0, n - 1, pos, newV);
    }

    int get(int x, int l, int r, int ll, int rr)
    {
        if(l > rr || r < ll)
            return 0;
        if(l >= ll && r <= rr)
            return t[x];

        int mid = (l + r) / 2;

        return max(get(x + x, l, mid, ll, rr), get(x + x + 1, mid + 1, r, ll, rr));
    }
    int get(int l, int r)
    {
        return get(1, 0, n - 1, l, r);
    }
};



void read()
{
    cin >> n >> S;
    for(int i = 0; i < n; ++i)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a, a + n);
}

long long getF(int k)
{
    segmetTree * sg = new segmetTree(n);

    for(int i = 0; i < n;)
    {
        int j;
        for(j = i; j < n && a[i].first == a[j].first; ++j)
        {
            int l = max(0, a[j].second - k), r = min(n - 1, a[j].second + k);

            ans[j] = sg -> get(l, r) + 1;
        }

        for(int q = i; q < j;)
        {
            int curMax = ans[q];
            int w;

            for(w = q + 1; w < j && a[w - 1].second + k >= a[w].second; ++w)
                curMax = max(curMax, ans[w]);

            for(int i = q; i < w; ++i)
                ans[i] = curMax;

            q = w;
        }

        for(; i < j; ++i)
            sg -> up(a[i].second, ans[i]);
    }

    long long res = 0;
    for(int i = 0; i < n; ++i)
        res += ans[i];

    return res;
}

void solve()
{
    int l = 0, r = n, ans = -1;

    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(getF(mid) <= S)
        {
            ans = mid;
            l = mid + 1;
        }else
            r = mid - 1;
    }

    cout << ans + 1 << '\n';
}

int main()
{
//    freopen("input.txt", "r", stdin);
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t --> 0)
    {
        read();
        solve();
    }

    return 0;
}