#include <bits/stdc++.h>
#define deb cout << "in " << __LINE__ << "\t: "
using namespace std;
#define int long long
int n, C, a[100010], b[100010], s[100010], t[20][100010], lst[100010];
#define lg(x) (31 ^ __builtin_clz(x))
int query(int l, int r) {
	int len = lg(r - l + 1);
	return __gcd(t[len][l], t[len][r - (1 << len) + 1]);
}
vector<pair<int, int>> p[100010];
int tr[100010], dp[100010];
void add(int x, int y) {
	for (; x <= n; x += x & -x)
		tr[x] = min(tr[x], y);
}
int getmn(int x, int res = 1e18) {
	x = min(x, n);
	for (; x; x -= x & -x)
		res = min(res, tr[x]);
	return res;
}
void Solve(int test) {
	cin >> n >> C;
	for (int i = 1; i <= n; i++)
		cin >> a[i], t[0][i] = a[i], tr[i] = 1e18, dp[i] = 1e18, p[i].clear();
	for (int i = 1; i <= n; i++)
		cin >> b[i], s[i] = s[i - 1] + b[i];
	for (int i = 0; i < 18; i++)
		for (int j = 1; j + (2 << i) - 1 <= n; j++)
			t[i + 1][j] = __gcd(t[i][j], t[i][j + (1 << i)]);
	for (int i = 1; i <= n; i++) {
		int l = 0, r = i;
		while (l < r) {
			int mid = (l + r + 1) / 2;
			if (query(mid, i) <= i - mid + 1)
				l = mid;
			else r = mid - 1;
		}
		lst[i] = l;
		if (l) p[l].push_back({i, query(l, i)});
	}
	add(1, 0);
	for (int i = 1; i <= n; i++) {
		for (auto [r, x] : p[i])
			dp[r] = getmn(x) + C + (s[r] - s[i - 1]) * x;
		if (lst[i]) add(i - lst[i] + 1, dp[i]);
	}
	int res = 1e18;
	for (int i = 1; i <= n; i++)
		res = min(res, dp[i]);
	cout << res << "\n";
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	for (int i = 1; i <= T; i++) Solve(i);
	return 0;
}