PLANTS

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF (1<<29)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define REP(i, n) FOR(i, 0, n)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define LG (17)
#define MX (1<<LG)
#define P2(v) (!(v&(v-1)))
struct RM{
    int dp[MX][LG+2],G[MX],XX,O=-1;
    void ini(int *A,int n){
        if(!XX++)FT(1,MX)G[k]=O+=P2(k);
        F(n)dp[i][0]=i;
        FT(1,k-(1<<k)+n+1)F(n+1-(1<<k))
            if(A[dp[i][k-1]]<A[dp[i+(1<<(k-1))][k-1]])
                dp[i][k]=dp[i][k-1];
            else dp[i][k]=dp[i+(1<<(k-1))][k-1];
    }
    int qy(int *A,int L,int R){
        int j(G[R-L+1]);
        if(A[dp[L][j]]<=A[dp[R-(1<<j)+1][j]])
            return A[dp[L][j]];
        return A[dp[R-(1<<j)+1][j]];
    }
}M;
struct RX{
    int dp[MX][LG+2],G[MX],XX,O=-1;
    void ini(int *A,int n){
        if(!XX++)FT(1,MX)G[k]=O+=P2(k);
        F(n)dp[i][0]=i;
        FT(1,k-(1<<k)+n+1)F(n+1-(1<<k))
            if(A[dp[i][k-1]]>A[dp[i+(1<<(k-1))][k-1]])
                dp[i][k]=dp[i][k-1];
            else dp[i][k]=dp[i+(1<<(k-1))][k-1];
    }
    int qy(int *A,int L,int R){
        int j(G[R-L+1]);
        if(A[dp[L][j]]>=A[dp[R-(1<<j)+1][j]])
            return A[dp[L][j]];
        return A[dp[R-(1<<j)+1][j]];
    }
}X;
int A[MX],N,K,D,W,B;
int main(void){
    IN(tt)F(tt){
        scanf("%d%d",&N,&K),assert(K>-1&&N>-1&&K<=1e5&&N<=1e5),ga(N,A),M.ini(A,N),X.ini(A,N),K=min(K+1,N-1),W+=N,B=0;
        F(N-K)B=max(B,X.qy(A,i,i+K)-M.qy(A,i,i+K));
        printf("%d\n",B);
    }
    assert(W<=3e6);
    return 0;
}