#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
// using i128 = __int128;
// using u128 = unsigned __int128;

inline void solve() {
    int n;
    i64 c, ans = LLONG_MAX;
    std::cin >> n >> c;
    std::vector<int> a(n + 1);
    std::vector<i64> b(n + 1), s(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= n; i++) {
        std::cin >> b[i];
        s[i] = s[i - 1] + b[i];
    }

    std::vector<std::vector<std::pair<int, i64>>> dp(n + 1);
    dp[0].emplace_back(0, 0);

    std::vector<std::pair<int,int>> p(20), empty(20) , tmp(20);//log n=20

    //get gcd
    //直接存下所有different gcd和其左端点即可
    for (int i = 1; i <= n; i++) {
        tmp = empty;
        for (auto &[w, v] : p) {
            int nw = std::__gcd(w, a[i]);
            if (tmp.empty()) {
                tmp.emplace_back(nw, v);
            } else if (p.back().first ^ nw) {
                tmp.emplace_back(nw, v);
            }
        }
        if (tmp.empty()) {
            tmp.emplace_back(a[i], i);
        } else if (tmp.back().first ^ a[i]) {
            tmp.emplace_back(a[i], i);
        }
        std::swap(p, tmp);

        int len = p.size();
        std::vector<std::pair<int, i64>> tp(len);
        for (int j = 0; j < len; j++) {
            auto [w, l] = p[j];
            int r = i;
            if (j + 1 < len) r = p[j + 1].second;
            int ll = i - w + 1;
            if (ll < l || ll > r) {
                continue;
            }
            int kk = ll - 1;
            auto &v = dp[kk];
            int L = 0, R = (int)v.size() - 1, pos = -1;
            while (L <= R) {
                int mid = (L + R) >> 1;
                if (v[mid].first <= w) {
                    pos = mid;
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            if(pos >= 0){
                i64 val = v[pos].second + (i64)w * (s[i] - s[kk]) + c;
                tp.emplace_back(w, val);
            }
        }
        if(tp.empty()) {
            dp[i].clear();
        } else {
            sort(tp.begin(), tp.end(), [](auto &x, auto &y){return x.first < y.first;});
            for (int i = 1; i < (int)tp.size(); i++) {
                tp[i].second = std::min(tp[i].second, tp[i-1].second);
            }
            dp[i].swap(tp);
            ans = std::min(ans, dp[i].back().second);
        }
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    
    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}