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

template <class S>
struct persistent {
	#define add emplace_back
	struct Node {
		int ls, rs;
		S info;
		Node() {}
		Node(int a, int b, S c): ls(a), rs(b), info(c) {}
	};
	std::vector<Node> tr;
	std::vector<int> root;
	int version, n;
	persistent() {
		version = 0, n = 1 << 30;
		tr.add(0, 0, 1ll << 60), root.add(0);
	}
	persistent(int n): persistent(vector<S>(n, 1ll << 60)) {}
	persistent(vector<S> t) { init(t); }
	void clear() {
		vector<Node>().swap(tr), vector<int>().swap(root);
		assert(tr.empty()), assert(root.empty());
		init(vector<S>(n, 1ll << 60));
	}
	void init(vector<S> t) {
		version = 0, n = t.size(), tr.add();
		auto build = [&](auto rec, int l, int r) -> int {
			tr.add(0, 0, 1ll << 60); int u = tr.size() - 1;
			if (l == r) return tr[u].info = t[l], u;
			int mid = l + r >> 1;
			tr[u].ls = rec(rec, l, mid), tr[u].rs = rec(rec, mid + 1, r);
			tr[u].info = tr[tr[u].ls].info + tr[tr[u].rs].info;
			return u;
		};
		root.add(build(build, 0, n - 1));
	}
	void set(int x, S t, bool ok = true) {
		auto modify = [&](auto rec, int u, int l, int r) -> int {
			tr.add(tr[u]); int v = tr.size() - 1;
			if (l == r) return tr[v].info = t, v;
			int mid = l + r >> 1;
			if (mid >= x) tr[v].ls = rec(rec, tr[u].ls, l, mid);
			else tr[v].rs = rec(rec, tr[u].rs, mid + 1, r);
			tr[v].info = tr[tr[v].ls].info + tr[tr[v].rs].info;
			return v;
		};
		if (ok) root.add(modify(modify, root[version ++], 0, n - 1));
		else root[version] = modify(modify, root[version], 0, n - 1);
	}
	S operator[] (pair<int, int> seg) {
		int L = seg.first, R = seg.second;
		auto query = [&](auto rec, int u, int l, int r) -> S {
			if (l >= L && r <= R) return tr[u].info;
			int mid = l + r >> 1;
			if (mid >= L && mid < R)
				return rec(rec, tr[u].ls, l, mid) + rec(rec, tr[u].rs, mid + 1, r);
			else if (mid >= L) return rec(rec, tr[u].ls, l, mid);
			else return rec(rec, tr[u].rs, mid + 1, r);
		};
		return query(query, root[version], 0, n - 1);
	}
	S operator[] (int x) {
		auto query = [&](auto rec, int u, int l, int r) -> S {
			if (l == r) return tr[u].info;
			int mid = l + r >> 1;
			if (mid >= x) return rec(rec, tr[u].ls, l, mid);
			else return rec(rec, tr[u].rs, mid + 1, r);
		};
		return query(query, root[version], 0, n - 1);
	}
	void unroll(int ver) {
		// assert(ver <= version);
		root.add(root[ver]), version ++;
	}
	#undef add
};

const i64 inf = 1ll << 60;
struct S {
	i64 v;
	S(): v(inf) {}
	S(i64 _v): v(_v) {}
	S operator+ (S T) { return min(v, T.v); }
};

const int maxn = 100005, maxlog = 17;

int n, C;
int a[maxn], b[maxn], c[maxn];
int ver[maxn], st[maxn][maxlog];

int GCD(int l, int r) {
	int k = __lg(r - l + 1);
	return __gcd(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int T;
	cin >> T;

	while (T -- ) {
		cin >> n >> C;
		for (int i = 1; i <= n; i ++)
			cin >> a[i], st[i][0] = a[i];
		for (int i = 1; i <= n; i ++)
			cin >> b[i], b[i] += b[i - 1];

		for (int j = 1; j <= __lg(n); j ++)
			for (int i = 1; i + (1 << j) - 1 <= n; i ++)
				st[i][j] = __gcd(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);

		persistent<S> dp(n + 1);
		dp.set(0, 0), ver[0] = dp.version;
		for (int i = 1; i <= n; i ++) {
			int cur = a[i], lim = i - 1;
			std::vector<int> sep = {i};
			while (1) {
				int lo = 1, ro = lim; lim = -1;
				while (lo <= ro) {
					int mid = lo + ro >> 1;
					if (GCD(mid, i) != cur) lo = mid + 1, lim = mid - 1;
					else ro = mid - 1;
				}
				if (lim == -1) break;
				sep.push_back(lim + 1), cur = GCD(lim + 1, i);
			}
			sep.push_back(0);
			assert(sep.size() <= maxlog + 1);
			for (int j = 0; j + 1 < sep.size(); j ++) {
				int v = GCD(sep[j], i), p = min(i - v + 1, sep[j]);
				if (p > sep[j + 1]) {
					int t = dp.version;
					dp.unroll(ver[p - 1]);
					i64 w = dp[{0, v}].v;
					dp.unroll(t);
					dp.set(i - p + 1, min(w + (i64)v * (b[i] - b[p - 1]) + C, dp[i - p + 1].v));
				}
			}
			ver[i] = dp.version;
		}

		// if (dp[{1, n}].v >= 1e16) cout << -1 << endl;
		cout << dp[{1, n}].v << endl;
	}


	return 0;
}