求hack

#include <bits/stdc++.h>
#define int long long
#define ld long double
#define ull unsigned long long
#define rep(i, n) for (int32_t i = 1; i <= (n); ++i)
#define re0d(i, n, d) for (int i = 0; i <= (n); i += d)
#define reb(i, n) for (int i = 0; i < (n); ++i)
#define re0(i, n) for (int i = 0; i <= (n); ++i)
#define re2(i, n) for (int i = 2; i <= (n); ++i)
#define lop(i, n) for (int i = (n); i; --i)
#define lob(i, n) for (int i = (n); ~i; --i)
#define hh(i, a, b) for (int i = (a); i <= (b); ++i)
#define pb push_back
#define eb emplace_back
#define mem(a, b) memset(a, b, sizeof a)
#define cpy(a, b) memcpy(a, b, sizeof a)
#define ppct __builtin_popcount
#define pii pair<int, int>
#define X first
#define Y second
#define FILEIN(s) freopen(s ".in", "r", stdin)
#define FILEOUT(s) freopen(s ".out", "w", stdout)
#define FILE(s) FILEIN(s), FILEOUT(s)
#define ls rt << 1
#define rs rt << 1 | 1
#define lson l, m, ls
#define rson m + 1, r, rs
#define mod wqx
#define prq priority_queue
#define pair32 pair<int32_t, int32_t>
#define mkp make_pair
#define lb lower_bound
using namespace std;
int INDEX__;
const int mod = (29ull<<57)+1;
const __int128 inv=(mod+1)/2;
void cmax(int &a, int b)
{
	if (a < b)
		a = b;
}
void cmin(int &a, int b)
{
	if (a > b)
		a = b;
}
double Time() { return 1. * clock() / CLOCKS_PER_SEC; }
void Add(int &a, int b) { (a += b) %= mod; }
void Del(int &a, int b)
{
	(a -= b % mod) %= mod;
	(a += mod) %= mod;
}
int p2w(int a) { return a * a; }
int qp(int a, int b = mod - 2)
{
	int s = 1;
	a %= mod;
	for (; b; b >>= 1, (a *= a) %= mod)
		if (b & 1)
			(s *= a) %= mod;
	return s;
}
const int N = 10005, INF = 1e18;
struct clearablearray
{
	int a[N], col[N];
	int &operator[](int x)
	{
		if (col[x] != INDEX__)
			col[x] = INDEX__, a[x] = 0;
		return a[x];
	}
};
int n,a[N],D,tot;
bool check(int mid){
	__int128 now=0;
	rep(i,n)now+=a[i]/mid;
	return now>=D;
}
map<int,int>mp;
vector<int>wtf[N*50];
int solve()
{
	cin>>n>>D;
	rep(i,n)cin>>a[i];
	int l=1,r=360e9,ans=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1,ans=mid;
		else r=mid-1;
	}
	rep(i,n){
		rep(j,D){
			int x=a[i]/j;
			if(x>ans)continue;
			if(!mp[x])mp[x]=++tot;
			if(x*j==a[i])
			wtf[mp[x]].pb(j);
		}
	}
	int anss=D-1;
	rep(i,tot){
		sort(wtf[i].begin(),wtf[i].end());
		int res=D,kill=0;
		for(int v:wtf[i]){
			if(v<=res)res-=v,kill++;
		}
		wtf[i].clear();
		anss=min(anss,D-kill);
	}
	// if(INDEX__==35)cout<<"Case #"<<INDEX__<<": "<<anss/10<<' '<<anss/10<<'\n';
	// else 
	cout<<"Case #"<<INDEX__<<": "<<anss<<'\n';
	mp.clear();tot=0;
	return 0;
}
main()
{
	// FILE("txt");
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while (T--)
		++INDEX__, solve();
	return 0;
}