#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int N = 1e5+5;
const int Mod = 998244353;

int n, m, C, a[N];
int g[N][17], lg[N];
ll ans = 1e18, b[N];

int qry(int l, int r) {
    int len = lg[r - l + 1];
    return __gcd(g[l][len], g[r - (1 << len) + 1][len]);
}

struct seg {
    int l, r;
    int g, len;
    ll f, w;
};
vector<seg> P;
vector<int> L[N], R[N];

struct minBIT {
    ll T[N];
    inline void upd(int x, ll k) { for (; x <= n; x += lowbit(x)) T[x] = min(T[x], k); }
    inline ll qry(int x) { ll ret = 0; for (; x; x -= lowbit(x)) ret = min(ret, T[x]); return ret; }
} T;

void solve() {
    scanf("%d%d", &n, &C);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &b[i]), b[i] += b[i - 1];

    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = n; i; i--) {
        g[i][0] = a[i];
        for (int j = 1; i + (1 << j) - 1 <= n; j++)
            g[i][j] = __gcd(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
    }

    P.clear();
    for (int i = 1; i <= n; i++) {
        int lst = i - 1, cg = a[i];
        while (lst != n) {
            int l = lst + 1, r = n, nxt = l;

            cg = qry(i, l);
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (qry(i, mid) == cg) l = mid + 1, nxt = mid;
                else r = mid - 1;
            }
            int r1 = max(lst + 1, i + cg - 1);
            if (r1 <= nxt) {
                P.pb((seg) { i, r1, cg, r1 - i + 1, 0ll, cg * (b[r1] - b[i - 1]) });
            }
            lst = nxt;
        }
    }

    m = P.size();
    for (int i = 0; i < m; i++) {
        L[P[i].l].pb(i);
        R[P[i].r].pb(i);
        // printf("|%d %d %d %lld|\n", P[i].l, P[i].r, P[i].g, &P[i].w);
    }

    memset(T.T, 0x3f, sizeof(T.T));
    for (int i = 1; i <= n; i++) {
        for (int j : L[i])
            P[j].f = T.qry(P[j].g) + C + P[j].w;

        for (int j : R[i])
            T.upd(P[j].len, P[j].f);
    }

    ans = 1e18;
    for (int i = 0; i < m; i++)
        ans = min(ans, P[i].f);

    printf("%lld\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}