#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(x) setprecision(x)<<fixed
#define ss second
#define fori(v) for(lli i=0; i<v; i++)
#define forj(v) for(lli j=0; j<v; j++)
#define fork(v) for(lli k=0; k<v; k++)
#define forl(v) for(lli l=0; l<v; l++)
#define fort(v) for(lli t=0; t<v; t++)
#define forz(v) for(lli z=0; z<v; z++)
#define lli long long int
#define MAX 100100
#define double long double
#define pb push_back
int inf = pow(10,9);
lli modulo = pow(10,9)+7;
double eps = 1e-11;
ifstream in;
ofstream out;
//#define cin in
//#define cout out
int freq[MAX] = {};
int fir[MAX] = {}; // the left part
int sec[MAX] = {}; // right part
int arr[MAX] = {};
void init(){
	fori(MAX)
		freq[i] = 0, fir[i] = 0, sec[i] = 0;
} 
bool great(bool equal_case){ // returns if first sum > (or >= if equal_case==1) second sum, and reinitilizes first and second arrays to 0
	int gr = -1;
	for(int i=MAX-1; i>-1; i--){
		if(gr==-1){
			if(fir[i] > sec[i])
				gr = 1;
			else if(sec[i] > fir[i])
				gr = 0;
		}
		fir[i]=0, sec[i]=0;
	}
	if(equal_case)
		return (gr!=0);
	return (gr==1);
}
void deal(){
	int t;
	cin>>t;
	assert(t<=10);
	forl(t){
		init();
		int n,k;
		cin>>n>>k;
		assert(n<=pow(10,5));
		assert(k>=2);
		fori(n){
			cin>>arr[i];
			assert(arr[i]<=pow(10,5));
			assert(arr[i]>=0);
			freq[arr[i]]++;
		}
		int a = 0, b= n-1;
		while(a<b){	// returns first index where sum1 > sum2
			int c = (a+b)/2;
		//	cout<<a<<" "<<b<<endl;
			fori(c+1)
				fir[arr[i]]++;
			sec[0] = freq[0] - fir[0];
			fori(MAX-1){
				sec[i+1] = freq[i+1] - fir[i+1];
				sec[i+1] += sec[i]/k, sec[i]%=k;
				fir[i+1] += fir[i]/k, fir[i]%=k;
			}
			if(great(0))
				b=c;
			else
				a=c+1;
		}
		if(a==0){
			cout<<a+1<<'\n';
			continue;
		}
		if(a==n-1){
			cout<<a<<'\n';
			continue;
		}
		// find out if (left part >= right part) without a, if yes than output left (as if in a-1), otherwise right(as if in a) 
		fori(a)
			fir[arr[i]]++;
		sec[arr[a]]--;
		sec[0] = freq[0] - fir[0];
		fori(MAX-1){
			sec[i+1] += freq[i+1] - fir[i+1];
			sec[i+1] += sec[i]/k, sec[i]%=k;
			fir[i+1] += fir[i]/k, fir[i]%=k;
		}
		if(great(1))
			cout<<a<<'\n';
		else
			cout<<a+1<<'\n';
	}
}
int main(){
//	freopen("i_test.txt", "r", stdin);
//	freopen("o5.txt", "wb", stdout);
	deal();
} 
// 10 3 2 1 1 1