#include <bits/stdc++.h>

using namespace std;

struct node {
  long long g, s;
};

int T, n, C;
vector<long long> a, b, pre;

long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  for (cin >> T; T--;) {
    cin >> n >> C, a.resize(n + 1), b.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    pre.resize(n + 1), pre[0] = 0;
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + b[i];
    vector<vector<node>> inv(n + 1);
    vector<node> p;
    for (int i = 1; i <= n; i++) {
      vector<node> cur;
      cur.push_back({a[i], i});
      for (const auto& [g, s] : p) {
        if (gcd(g, a[i]) == cur.back().g) {
          cur.back().s = s;
        } else {
          cur.push_back({gcd(g, a[i]), s});
        }
      }
      p = cur, inv[i] = cur;
    }
    vector<long long> k = {1}, v = {0};
    long long L_max = 1;
    for (int i = 1; i <= n; i++) {
      auto& intervals = inv[i];
      map<long long, long long> tmp;
      for (const auto& [g, s] : intervals) {
        if (i - s + 1 >= max(g, L_max)) {
          int pos = upper_bound(k.begin(), k.end(), g) - k.begin() - 1;
          if (pos >= 0) {
            if (tmp.count(i - s + 1)) {
              if (v[pos] + g * (pre[i] - pre[s - 1]) + C < tmp[i - s + 1]) {
                tmp[i - s + 1] = v[pos] + g * (pre[i] - pre[s - 1]) + C;
              }
            } else {
              tmp[i - s + 1] = v[pos] + g * (pre[i] - pre[s - 1]) + C;
            }
          }
        }
      }
      for (const auto& [len, val] : tmp) {
        if (len >= L_max) {
          if (k.empty() || len > k.back()) {
            k.push_back(len);
            if (v.empty()) {
              v.push_back(val);
            } else {
              v.push_back(min(v.back(), val));
            }
          } else {
            int pos = k.size() - 1;
            for (; pos >= 0 && k[pos] > len; pos--);
            if (pos >= 0 && k[pos] == len && val < v[pos]) {
              v[pos] = val;
              for (int j = pos; j < k.size(); j++) {
                if (j == 0) {
                  v[j] = val;
                } else {
                  v[j] = min(v[j - 1], val);
                }
              }
            }
          }
          L_max = max(L_max, len);
        }
      }
    }
    long long ans = 1e18;
    for (size_t i = 0; i < k.size(); i++) {
      if (k[i] >= 1) {
        ans = min(ans, v[i]);
      }
    }
    cout << ans << '\n';
  }
  return 0;
}