#include<bits/stdc++.h>
using namespace std;

vector<int> tab;

bool czy(int x,int n,int k)
{
    vector<int> lis;
    vector<int> dp(k+3,0);
    for(int i = 0;i < n;++i)
    {
        if(tab[i] >= x)
        {
            lis.push_back(1);
        }
        else
        {
            lis.push_back(0);
        }
    }
int d = (n%k) + ((n%k) == 0 ? n : 0);
    for(int i = n-1;i >= 0;i--)
    {
        int j = i%k;
        dp[j] = max(dp[j],(j+1 < d ? dp[j+1] : 0) + lis[i]);
//cout << dp[j] << " " << j << " dp\n";
    }
   // cout << dp[0] << " " << d << endl;
    if(dp[0] > d/2) return true;
    return false;
    //cout << dp[k-1] << endl;
}

int main()
{
    int t;
    cin >> t;
    for(int q = 0;q < t;++q)
    {
        int n,k,x;
        cin >> n >> k;    
		tab = {};
        for(int i = 0;i < n;++i)
        {
            cin >> x;
            tab.push_back(x);
        }
        //cout << czy(3,n,k);
        int l = 0,p=1000000003,mid;
//czy(6,n,k);
        while(l < p)
        {
            mid = (l+p+1)/2;
//cout << l << " " << p << " lr\n";
            if(czy(mid,n,k) == true)
            {
                l = mid;
            }
            else
            {
                p = mid-1;
            }
        }
        cout << l << endl;
    }
}