#include <bits/stdc++.h>
using namespace std;

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
using ll = long long;
using P = pair<int,int>;

int main() {
  FAST;
  
  int tc = 1, ti;
  cin >> tc;

  for (ti = 1; ti <= tc; ++ti) {
    int n, k, i, j, d, dd, g;
    cin >> n >> k;

    vector<int> a(n);
    for (i = 0; i < n; ++i) cin >> a[i];

    map<int,vector<int>> mp;
    for (i = 0; i < n; ++i) mp[a[i]].push_back(i);

    priority_queue<P, vector<P>, greater<P>> pq;
    vector<int> dis(n, INT_MAX);
    pq.emplace(0, 0);
    
    for (int z : mp[a[0]]) dis[z] = 1;
    dis[0] = 0;

    while (!pq.empty()) {
      tie(d, i) = pq.top(); pq.pop();
      if (dis[i] != d) continue;

      if (i < n-1) {
        dd = d+k;
        j = i+1;
        if (dis[j] > dd) {
          dis[j] = dd;
          pq.emplace(dd, j);
        }
      }

      for (j = i+1; j < n; ++j) {
        if (dis[j] <= d) continue;
        g = gcd(a[i], a[j]);
        dd = d + a[i]/g;
        if (dis[j] > dd) {
          for (int z : mp[a[j]]) {
            if (z <= i) continue;
            if (dis[z] > dd) {
              dis[z] = dd;
              pq.emplace(dd, z);
            }
          }
        }
      }
    }

    cout << dis[n-1] << "\n";
  }

  return 0;
}