// PIPRA ||  HABIB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define int        long long int
#define pb         push_back
#define all(x)     x.begin(),x.end()
#define allr(x)    x.rbegin(),x.rend()
#define ii         pair<int,int>
#define endl       "\n"

template<typename T>
ostream& operator<<(ostream &os, const vector<T> &v) { os << '{';
    for (const auto &x : v) os << " " << x;    return os << '}';  }
using orderedTree = tree<int, null_type, less<int>, 
    rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 5;
const int inf = 1e18;
vector<vector<int>> divs(N);

void prec(){
    for(int i=1 ; i<N ; i++){
        for(int j=i; j<N ; j+=i){
            divs[j].pb(i);
        }
    }
}

void pipra(){
    int n, k;  cin >> n >> k;
    vector<int> a(n);
    for(int i=0 ; i<n ; i++)
        cin >> a[i];

    vector<int> dp(n+1, inf);
    vector<int> dist(N, inf);

    dp[0] = 0;
    for(auto d: divs[a[0]]){
        dist[d] = a[0] / d;
    }

    for(int i=1 ; i<n ; i++){
        dp[i] = dp[i-1] + k;

        for(auto d: divs[a[i]]){
            dp[i] = min(dp[i], dist[d]);
        }
        for(auto d: divs[a[i]]){
            dist[d] = min(dist[i], dp[i] + (a[i]/d));
        }
    }

    cout << dp[n-1] << endl;
}

int32_t main(){
    // HABIB
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

    prec();

    int t;    cin>>t;
    while(t--) {
        pipra();
    }
    return 0 ;
}