#include <iostream>
#include <vector>
#include <queue>
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

#define int long long 

const int N = 2e5+1000;

int n , m ;

struct node{
    int value;
    int id;
    int rank ;
} a[N];

int ans = 0;
int tr[N];

int lowbit(int x){
    return -x & x;
}

int sum(int x){
    int ret = 0;
    for(int i = x ; i ; i -= lowbit(i)) ret += tr[i];
    return ret ;
}

void add(int x , int c ){
    for(int i = x ; i <= n ; i += lowbit(i)) tr[i] += c ;
}

bool cmp1(node a, node b ){
   if(a.value == b.value){
       return a.id < b.id;
   } 
   return a.value > b.value;
}

bool cmp2(node a , node b){
    return a.id < b.id;
}

bool check(int maxx){
    
    // for(int i = 1 ;i <= n ; i++) tr[i] = 0;
    //cout << endl;
    int cnt = 0 ;
    int l = 1 ,  r = 1;
    int t_sum = 0 ;
    //cout << maxx <<endl;
    while( r <= n ){
        // add(a[i].r , 1);
        int now = sum(a[r].rank - 1);
        //printf("t_sum = %d now = %d" , t_sum , now);
        //cout << "t_sum = " << t_sum << " now = " << now << endl;
        if(cnt > m) return false;
        if(t_sum + now <= maxx){
            //cout << "#" << l << " " << r << endl; 
            t_sum += now;
            add(a[r].rank , 1 );
            //cout << a[r].rank << " +1" << endl;
            r ++;
        }
        else{
            cnt ++ ;
            //cout << l << " " << r-1 << endl;
            for(int i = l; i <= r - 1 ; i++) {
                //cout << a[i].rank << " -1 " << endl;
                add(a[i].rank , -1 );
            }
            
            l = r;
            
            t_sum = 0;
        }
    }
    
    for(int i = l; i <= n ; i++) add(a[i].rank , -1);
    
    cnt ++ ;
    if(cnt <= m) {
        // ans = min(ans , cnt);
        return true;
    }
    return false;
}

void solve(){
    cin >> n >> m ;
    if(m >= n || n == 1) {
        cout << 0 << endl;
        return ;
    }
    ans = m;
    for(int i = 1 ;i <= n ; i++) cin >> a[i].value , a[i].id = i , tr[i] = 0;
    
    sort(a + 1 , a + 1 + n , cmp1);
    
    for(int i = 1 ;i <= n ; i ++) {
    
        if(a[i].value == a[i-1].value)
            a[i].rank = a[i-1].rank;
        else
            a[i].rank =a[i-1].rank+1;
    }
    
    sort(a + 1 ,a + 1 + n , cmp2);
    
    int l = 0 , r = n * n;
    while( l < r){
        int mid = (l + r) >> 1;
        if(check(mid)){
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    
    // cout << ans << endl;
    cout << l << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t ;
    cin >> t ;
    while(t  -- ) {
        solve();
    }
    return 0;
}