#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class T>
void ckmn(T &a, T b) {
	a = min(a, b);
}
template <class T>
T gcd(T a, T b) {
	return !b ? a : gcd(b, a % b);
}
/*
主席树维护 i 结尾，最后一个区间长度 =j 的最小代价
ST 表维护区间 gcd
*/
const int maxn = 1e5 + 5;
int n;
ll C;
int a[maxn];
ll b[maxn];
ll preb[maxn];
ll wb(int l, int r) {
	return preb[r] - preb[l - 1];
}
struct ST {
	int _gcd[18][maxn];
	void init() {
		for (int i = 1; i <= n; i++) {
			_gcd[0][i] = a[i];
		}
		for (int i = 1; i <= 17; i++) {
			for (int j = 1; j <= n - (1 << i) + 1; j++) {
				_gcd[i][j] = gcd(_gcd[i - 1][j], _gcd[i - 1][j + (1 << i - 1)]);
			}
		}
	}
	int qgcd(int l, int r) {
		int _ = __lg(r - l + 1);
		return gcd(_gcd[_][l], _gcd[_][r - (1 << _) + 1]);
	}
} st;
struct HJT {
	struct Node {
		int ls, rs;
		ll mn;
	} nd[32400005];
	// 1e5*(18^2)
	int ndcnt;
	void pushup(Node &x) {
		x.mn = min(nd[x.ls].mn, nd[x.rs].mn);
	}
	void bd(int &rt, int l, int r) {
		if (!rt)
			rt = ++ndcnt;
		nd[rt].mn = 1e18;
		if (l == r) {
			return;
		}
		int mid = (l + r >> 1);
		bd(nd[rt].ls, l, mid);
		bd(nd[rt].rs, mid + 1, r);
	}
	void chg(int &rtold, int &rtnew, int l, int r, int x, ll _v) {
		if (!rtnew) {
			rtnew = ++ndcnt;
			nd[rtnew].mn = nd[rtold].mn;
		}
		if (l == r) {
			ckmn(nd[rtnew].mn, _v);
			return;
		}
		int mid = (l + r >> 1);
		if (mid >= x) {
			if (nd[rtnew].ls == nd[rtold].ls)
				nd[rtnew].ls = 0; // 这个节点需要新建
			chg(nd[rtold].ls, nd[rtnew].ls, l, mid, x, _v);
		} else {
			if (nd[rtnew].rs == nd[rtold].rs)
				nd[rtnew].rs = 0; // 同理
			chg(nd[rtold].rs, nd[rtnew].rs, mid + 1, r, x, _v);
		}
		if (!nd[rtnew].ls)
			nd[rtnew].ls = nd[rtold].ls;
		if (!nd[rtnew].rs)
			nd[rtnew].rs = nd[rtold].rs;
		pushup(nd[rtnew]);
	}
	ll qmn(int rt, int curl, int curr, int l, int r) {
		if (!rt)
			return 1e18;
		if (curl >= l && curr <= r) {
			return nd[rt].mn;
		}
		int mid = (curl + curr >> 1);
		ll ans = 1e18;
		if (mid >= l)
			ckmn(ans, qmn(nd[rt].ls, curl, mid, l, r));
		if (mid < r)
			ckmn(ans, qmn(nd[rt].rs, mid + 1, curr, l, r));
		return ans;
	}
} hjt;
int rt[maxn];
void solve(int id_of_test) {
	cin >> n >> C;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	st.init();
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		preb[i] = preb[i - 1] + b[i];
	}
	hjt.bd(rt[0], 1, 100000);
	for (int r = 1; r <= n; r++) {
		rt[r] = ++hjt.ndcnt;
		hjt.nd[rt[r]] = hjt.nd[rt[r - 1]];
		int ok = 0;
		int efl = 1, efr = r;
		while (efl <= efr) {
			int mid = (efl + efr >> 1);
			if (r - mid + 1 >= st.qgcd(mid, r)) {
				ok = mid;
				efl = mid + 1;
			} else {
				efr = mid - 1;
			}
		}
		if (!ok)
			continue; // 不存在合法的 l
		int l = ok;   // 最右边的合法的 l
		int _gcd = st.qgcd(l, r);
		while (l >= 1) {
			if (r - l + 1 >= _gcd) {
				// 合法，计算答案
				ll sum = 1ll * _gcd * wb(l, r);
				ll ans = sum;
				ckmn(ans, sum + C + hjt.qmn(rt[l - 1], 1, 100000, 1, _gcd));
				hjt.chg(rt[r - 1], rt[r], 1, 100000, r - l + 1, ans);
			}
			// 目前 l 是本 gcd 同色块的右端点
			int efl = 1, efr = l;
			int ok = l;
			while (efl <= efr) {
				int mid = (efl + efr >> 1);
				int k = __lg(r - mid + 1);
				if (st._gcd[k][mid] % _gcd != 0 || st._gcd[k][r - (1 << k) + 1] % _gcd != 0) {
					efl = mid + 1;
				} else {
					ok = mid;
					efr = mid - 1;
				}
			}
			// ok 就是本 gcd 同色块的左端点
			l = ok - 1;
			if (l)
				_gcd = st.qgcd(l, r);
		}
	}
	cout << hjt.qmn(rt[n], 1, 100000, 1, 100000) + C << '\n';
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	for (int _ = 1; _ <= T; _++) {
		solve(_);
	}
	return 0;
}