#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;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZlY3RvcjxpbnQ+IHRhYjsKCmJvb2wgY3p5KGludCB4LGludCBuLGludCBrKQp7CiAgICB2ZWN0b3I8aW50PiBsaXM7CiAgICB2ZWN0b3I8aW50PiBkcChrKzMsMCk7CiAgICBmb3IoaW50IGkgPSAwO2kgPCBuOysraSkKICAgIHsKICAgICAgICBpZih0YWJbaV0gPj0geCkKICAgICAgICB7CiAgICAgICAgICAgIGxpcy5wdXNoX2JhY2soMSk7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGxpcy5wdXNoX2JhY2soMCk7CiAgICAgICAgfQogICAgfQppbnQgZCA9IChuJWspICsgKChuJWspID09IDAgPyBuIDogMCk7CiAgICBmb3IoaW50IGkgPSBuLTE7aSA+PSAwO2ktLSkKICAgIHsKICAgICAgICBpbnQgaiA9IGklazsKICAgICAgICBkcFtqXSA9IG1heChkcFtqXSwoaisxIDwgZCA/IGRwW2orMV0gOiAwKSArIGxpc1tpXSk7Ci8vY291dCA8PCBkcFtqXSA8PCAiICIgPDwgaiA8PCAiIGRwXG4iOwogICAgfQogICAvLyBjb3V0IDw8IGRwWzBdIDw8ICIgIiA8PCBkIDw8IGVuZGw7CiAgICBpZihkcFswXSA+IGQvMikgcmV0dXJuIHRydWU7CiAgICByZXR1cm4gZmFsc2U7CiAgICAvL2NvdXQgPDwgZHBbay0xXSA8PCBlbmRsOwp9CgppbnQgbWFpbigpCnsKICAgIGludCB0OwogICAgY2luID4+IHQ7CiAgICBmb3IoaW50IHEgPSAwO3EgPCB0OysrcSkKICAgIHsKICAgICAgICBpbnQgbixrLHg7CiAgICAgICAgY2luID4+IG4gPj4gazsgICAgCgkJdGFiID0ge307CiAgICAgICAgZm9yKGludCBpID0gMDtpIDwgbjsrK2kpCiAgICAgICAgewogICAgICAgICAgICBjaW4gPj4geDsKICAgICAgICAgICAgdGFiLnB1c2hfYmFjayh4KTsKICAgICAgICB9CiAgICAgICAgLy9jb3V0IDw8IGN6eSgzLG4sayk7CiAgICAgICAgaW50IGwgPSAwLHA9MTAwMDAwMDAwMyxtaWQ7Ci8vY3p5KDYsbixrKTsKICAgICAgICB3aGlsZShsIDwgcCkKICAgICAgICB7CiAgICAgICAgICAgIG1pZCA9IChsK3ArMSkvMjsKLy9jb3V0IDw8IGwgPDwgIiAiIDw8IHAgPDwgIiBsclxuIjsKICAgICAgICAgICAgaWYoY3p5KG1pZCxuLGspID09IHRydWUpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGwgPSBtaWQ7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwID0gbWlkLTE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dCA8PCBsIDw8IGVuZGw7CiAgICB9Cn0=