workout

#include <bits/stdc++.h>

using namespace std;
#define mod     1000000007
#define ll      long long
#define pb      push_back
#define pob     pop_back
#define pq      priority_queue<int>
#define pii     pair<int,int>
#define ff      first
#define ss      second
#define vi      vector<int>

void fastIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int findSegments(vector<ll> diff,ll x){

    int k=0;

    // ex- 1,4,6,10 and mid=5 , so we start from index of 6
    int i=upper_bound(diff.begin(),diff.end(),x)-diff.begin();
    for(;i<diff.size();i++)
        k+=ceil(diff[i]/x)-1;
    return k;
}
int main() {

    fastIO();
    int t,itr=1;
    cin >> t;
    while (itr<=t) {

        int n,req_k,curr_k;
        cin>>n>>req_k;
        vector<ll> arr(n),diff(n-1);
        for(ll &i:arr)
            cin>>i;
        for(int i=0;i<n-1;i++){
            diff[i]=arr[i+1]-arr[i];
        }

        sort(diff.begin(),diff.end());
        if(req_k==1){
            if(n==1)
                printf("Case #%d: %lld\n",itr,diff[0]/2);
            else {
                ll d1=diff[diff.size()-1],d2=diff[diff.size()-2];
                d1/=2;
                printf("Case #%d: %lld\n",itr,((d1>d2)?d1:d2));
            }
        }else{

            ll start=diff[0],end=diff[diff.size()-1],mid=0;

            while(start<end){
                mid=start+(end-start)/2;

                //find no of k's req to satisfy diff=mid
                curr_k=findSegments(diff,mid);

                if(curr_k>req_k)
                    start=mid+1;
                else    end=mid;    //we want immediate right
            }
            printf("Case #%d: %lld\n",itr,start);
        }
        itr++;
    }
    return 0;
}