PLANTS-SONGMAN

#include <bits/stdc++.h>

using namespace std;
using LINT = long long int;
using PII = pair<int,int>;

#define PB push_back
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)

int t;
int n,k;

int arr[100007];

void process(){
    cin>>n>>k;
    REP(i,n)cin>>arr[i];

    multiset<int> pp;

    for(int i = 0; i < min(k+2,n); ++i)
        pp.insert(arr[i]);
    int best = 0;
    REP(i,n){
        best = max(best,*pp.rbegin()-arr[i]);
        if(i+k+2<n)
            pp.insert(arr[i+k+2]);
        if(i-k-1>=0)
            pp.erase(pp.find(arr[i-k-1]));
    }
    cout<<best<<endl;
}

int main() {
    cin>>t;
    while(t--)process();
    return 0;
}