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

typedef long long ll;

// Constants
const int MAX_A = 200005;
const ll INF = 1e18;

// Precompute all divisors for each number up to MAX_A
vector<vector<int>> all_divisors(MAX_A, vector<int>());
void precompute_divisors() {
    for(int g = 1; g < MAX_A; ++g){
        for(int multiple = g; multiple < MAX_A; multiple += g){
            all_divisors[multiple].push_back(g);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    precompute_divisors();
    
    int T;
    cin >> T;
    
    // Initialize min_cost and last_update
    vector<ll> min_cost(MAX_A, INF);
    vector<int> last_update(MAX_A, 0);
    int current_testcase = 1;
    
    while(T--){
        int N, K;
        cin >> N >> K;
        vector<int> A(N+1, 0); // 1-based indexing
        for(int i=1; i<=N; ++i){
            cin >> A[i];
        }
        
        // Initialize DP array
        vector<ll> dp(N+1, INF);
        dp[1] = 0;
        
        // Update min_cost for the first position
        for(auto &g : all_divisors[A[1]]){
            ll temp = dp[1] + (ll)A[1] / g;
            if(last_update[g] != current_testcase || temp < min_cost[g]){
                min_cost[g] = temp;
                last_update[g] = current_testcase;
            }
        }
        
        // Iterate through positions 2 to N
        for(int i=2; i<=N; ++i){
            // Option 1: Move from i-1 to i with cost K
            ll min_val = dp[i-1] + (ll)K;
            
            // Option 2: Jump from any j with GCD(A[j], A[i]) = g
            for(auto &g : all_divisors[A[i]]){
                if(last_update[g] == current_testcase){
                    min_val = min(min_val, min_cost[g]);
                }
            }
            
            dp[i] = min_val;
            
            // Update min_cost for all divisors of A[i]
            for(auto &g : all_divisors[A[i]]){
                ll temp = dp[i] + (ll)A[i] / g;
                if(last_update[g] != current_testcase || temp < min_cost[g]){
                    min_cost[g] = temp;
                    last_update[g] = current_testcase;
                }
            }
        }
        
        cout << dp[N] << "\n";
        current_testcase++;
    }
    
    return 0;
}