#include <bits/stdc++.h>
#define N 1000000
using namespace std;
int t, n, k, a[N + 1];
int zp[N * 2], cnt, b[N * 2], fa[N * 2];
bool hg[N * 2];
vector<int> mul[N * 2];
set<int> pr;
int get_fa(int nd);
void merge(int x, int y);
int main() {
	memset(hg, false, sizeof(hg));
	for (int i = 2; i < N * 2; i++) {
		if (hg[i] == false) {
			cnt++;
			zp[cnt] = i;
			for (int j = i + i; j < N * 2; j += i) {
				hg[i] = true;
			}
		}
	}
	scanf("%d", &t);
	memset(mul, 0, sizeof(mul));
	while (t--) {
		scanf("%d%d", &n, &k);
		long long sum = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
			if (a[i] == 1) {
				sum++;
			}
			b[i - 1] = a[i];
			b[i - 1 + n] = a[i];
		}
		sum *= n;
		n *= 2;
		pr.clear();
		for (int i = 1; i < n; i++) {
			fa[i] = i;
			int tmp = b[i];
			for (int j = 1; zp[j] * zp[j] <= tmp; j++) {
				if (tmp % zp[j] == 0) {
					pr.insert(zp[j]);
					mul[zp[j]].push_back(i);
				}
				while (tmp % zp[j] == 0) {
					tmp /= zp[j];
				}
			}
			if (tmp != 1) {
				pr.insert(tmp);
				mul[tmp].push_back(i);
			}
		}
		for (int i : pr) {
			int lst = 0;
			for (int j : mul[i]) {
				if (lst != 0 && j - lst <= k) {
					merge(j, lst);
				}
				lst = j;
			}
			mul[i].clear();
		}
		for (int i = 1; i < n; i++) {
			if (b[i] != 1 && fa[i] == i) {
				sum += 1;
			}
		}
		printf("%lld\n", sum);
	}
	return 0;
}
int get_fa(int nd) {
	if (fa[nd] == nd) {
		return nd;
	}
	fa[nd] = get_fa(fa[nd]);
	return fa[nd];
}
void merge(int x, int y) {
	fa[get_fa(x)] = get_fa(y);
	return;
}