#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, k, A[200005], vs[200005];

void solve(){
	cin >> n >> k;
	for(int i = 1; i <= n; i++)cin >> A[i], vs[i] = 0;
	int bnd = min(k * (n - 1), A[1] / __gcd(A[1], A[n]));
	queue <int> q[bnd + 1];
	q[0].push(1);
	for(int i = 0; i <= bnd; i++){
		while(!q[i].empty()){
			int j = q[i].front(); q[i].pop();
			if(j == n){
				cout << i << '\n';
				return;
			}
			if(vs[j])continue;
			vs[j] = 1;
			int mn = min(k * (n - j), A[j] / __gcd(A[j], A[n]));
			for(int kk = j + 1; kk <= n; kk++){
				int tot = A[j] / __gcd(A[j], A[kk]);
				if(tot > mn || i + tot > bnd)continue;
				q[i + tot].push(kk);
			}
			if(i + k <= bnd)q[i + k].push(j + 1);
		}
	}
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}