#include <math.h>
#include <assert.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <array>
#include <random>
#include <chrono>
#include <climits>
#include <bitset>
#include <unordered_map>
using namespace std ;
#define int long long
#define ii pair<int,int>
#define ar array
#define sz(x) ((int)(x).size())
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define rep(i, a, b) for (int i=a; i<(b); i++)
#define forn(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define ford(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define FAST_IO ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
template<class T> bool gmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool gmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int N = 200200;
const int INF = 1e10 ;
/* Print pair */
template <typename T,typename S>
ostream & operator << (ostream &os , const pair<T,S> &v) {
    os << "(" ;
    os << v.first << "," << v.second << ")" ;
    return os ;
}
/* Print vector */
template <typename T>
ostream & operator << (ostream &os , const vector<T> &v) {
    os << "[" ;
    int sz = v.size() ;
    for(int i = 0 ; i < sz ; ++i) {
        os << v[i] ;
        if(i!=sz-1)os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print set */
template <typename T>
ostream & operator << (ostream &os , const set<T> &v) {
    T last = *v.rbegin() ;
    os << "[" ;
    for(auto it : v) {
        os << it  ;
        if(it != last) os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print Map */
template <typename T,typename S>
ostream & operator << (ostream &os , const map<T,S> &v) {
    for(auto it : v) {
        os << it.first << " : " << it.second << "\n" ;
    }
    return os ;
}
//debug
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif


template <typename type>
struct SegmentTreeNonLazy
{
    #define Mid ((L + R) >> 1)
    #define Left (Node << 1)
    #define Right (Node << 1 | 1)
 
    private : const type E = {INF, N} ;         /// identity element        /// Check this
    private : static const int Nax = 4 * N;                         /// Check this
 
    public : int n;    /// Array length
    private : type Tree[Nax];
 
    public : SegmentTreeNonLazy(int n = 0) : n(n)
    {
        for(int Node = 0; Node < 4 * n ; Node++)
            Tree[Node] = E;
    }
 
    private : type Unite(type x, type y)    /// Check this
    {
        return min(x, y);
    }
 
    private : void Merge(int Node)
    {
        Tree[Node] = Unite(Tree[Left], Tree[Right]);
    }
 
    public : void Build(const vector <type>& a)
    {
        Clear();
        n = a.size();
        Build(a, 1, 0, n - 1);
    }
 
    private : void Build(const vector <type>& a, int Node, int L, int R)
    {
        Tree[Node] = E;
        if(L == R)  return void(Tree[Node] = a[L]);
 
        Build(a, Left, L, Mid);
        Build(a, Right, Mid + 1, R);
 
        Merge(Node);
    }
 
    public : void Update(int i, type x)
    {
        if(0 > i || i >= n) return ;
        Update(i, x, 1, 0, n - 1);
    }
 
    private : void Update(int i, type x, int Node, int L, int R)
    {
        if(L == R)          return void(Tree[Node] = x);    /// Check This
 
        if(i <= Mid)    Update(i, x, Left, L, Mid);
        else            Update(i, x, Right, Mid + 1, R);
 
        Merge(Node);
    }
 
    public : type Query(int i, int j)
    {
        if(i < 0)   i = 0;
        if(j >= n)  j = n - 1;
        if(n <= 0 || i > j) return E;
        return Query(i, j, 1, 0, n - 1);
    }
 
    private : type Query(int i, int j, int Node, int L, int R)
    {
        if(j < L || R < i)      return E;
        if(i <= L && R <= j)    return Tree[Node];
 
        return Unite(Query(i, j, Left, L, Mid), Query(i, j, Right, Mid + 1, R));
    }
 
    private : void Clear()
    {
        for(int Node = 0; Node <= 4 * n; Node++)
            Tree[Node] = E;
        n = 0;
    }
 
    #undef Mid
    #undef Left
    #undef Right
};
SegmentTreeNonLazy<ii> st ;
vector<ii> a ;
int n ,p ;
int dfs(int l , int r) {
	if(l >= r) return 0 ;

	auto [mn, idx] = st.Query(l,r) ;
	int left = idx , right = idx ;
	while(left >= l && a[left].first % mn == 0) left-- ;
	while(right <= r && a[right].first % mn == 0) right++ ;
	left++ ;
	right-- ;

	int ans = (right-left) * min(p, mn) ;
	if(left < idx) ans += dfs(l,left) ;
	else if(idx-1 >= l) ans += dfs(l,idx-1) + p ;
	if(idx < right) ans += dfs(right, r) ;
	else if(idx+1 <= r) ans += dfs(idx+1, r) + p ;
	return ans ;
}

void solve(){
	cin >> n >> p ;
	a.resize(n) ;
	st.n = n ;
	for(auto& x : a) cin >> x.ff ;
	forn(i,n) a[i].ss = i ;
	st.Build(a) ;
	cout << dfs(0,n-1) << endl ;
}


int32_t main(){
    FAST_IO ;
    int t = 1 ;
    cin >> t ;
    while(t--){
        solve() ;
    }
}

### Prompt

Please create a solution in Cpp to the following problem:

You are given an array a of n (n ≥ 2) positive integers and an integer p. Consider an undirected weighted graph of n vertices numbered from 1 to n for which the edges between the vertices i and j (i<j) are added in the following manner:

  * If gcd(a_i, a_{i+1}, a_{i+2}, ..., a_{j}) = min(a_i, a_{i+1}, a_{i+2}, ..., a_j), then there is an edge of weight min(a_i, a_{i+1}, a_{i+2}, ..., a_j) between i and j. 
  * If i+1=j, then there is an edge of weight p between i and j. 



Here gcd(x, y, …) denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers x, y, ....

Note that there could be multiple edges between i and j if both of the above conditions are true, and if both the conditions fail for i and j, then there is no edge between these vertices.

The goal is to find the weight of the [minimum spanning tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) of this graph.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases.

The first line of each test case contains two integers n (2 ≤ n ≤ 2 ⋅ 10^5) and p (1 ≤ p ≤ 10^9) — the number of nodes and the parameter p.

The second line contains n integers a_1, a_2, a_3, ..., a_n (1 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5. 

Output

Output t lines. For each test case print the weight of the corresponding graph.

Example

Input


4
2 5
10 10
2 5
3 3
4 5
5 2 4 9
8 8
5 3 3 6 10 100 9 15


Output


5
3
12
46

Note

Here are the graphs for the four test cases of the example (the edges of a possible MST of the graphs are marked pink):

For test case 1

<image>

For test case 2

<image>

For test case 3

<image>

For test case 4

<image>

### Response

```cpp
#include <math.h>
#include <assert.h>
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#include <cstring>
#include <functional>
#include <stack>
#include <array>
#include <random>
#include <chrono>
#include <climits>
#include <bitset>
#include <unordered_map>
using namespace std ;
#define int long long
#define ii pair<int,int>
#define ar array
#define sz(x) ((int)(x).size())
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n'
#define ff first
#define ss second
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define rep(i, a, b) for (int i=a; i<(b); i++)
#define forn(i, a) for (int i=0; i<(a); i++)
#define repd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define ford(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define FAST_IO ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
template<class T> bool gmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool gmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int N = 200200;
const int INF = 1e10 ;
/* Print pair */
template <typename T,typename S>
ostream & operator << (ostream &os , const pair<T,S> &v) {
    os << "(" ;
    os << v.first << "," << v.second << ")" ;
    return os ;
}
/* Print vector */
template <typename T>
ostream & operator << (ostream &os , const vector<T> &v) {
    os << "[" ;
    int sz = v.size() ;
    for(int i = 0 ; i < sz ; ++i) {
        os << v[i] ;
        if(i!=sz-1)os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print set */
template <typename T>
ostream & operator << (ostream &os , const set<T> &v) {
    T last = *v.rbegin() ;
    os << "[" ;
    for(auto it : v) {
        os << it  ;
        if(it != last) os << "," ;
    }
    os << "]\n" ;
    return os ;
}
/* Print Map */
template <typename T,typename S>
ostream & operator << (ostream &os , const map<T,S> &v) {
    for(auto it : v) {
        os << it.first << " : " << it.second << "\n" ;
    }
    return os ;
}
//debug
#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif


template <typename type>
struct SegmentTreeNonLazy
{
    #define Mid ((L + R) >> 1)
    #define Left (Node << 1)
    #define Right (Node << 1 | 1)
 
    private : const type E = {INF, N} ;         /// identity element        /// Check this
    private : static const int Nax = 4 * N;                         /// Check this
 
    public : int n;    /// Array length
    private : type Tree[Nax];
 
    public : SegmentTreeNonLazy(int n = 0) : n(n)
    {
        for(int Node = 0; Node < 4 * n ; Node++)
            Tree[Node] = E;
    }
 
    private : type Unite(type x, type y)    /// Check this
    {
        return min(x, y);
    }
 
    private : void Merge(int Node)
    {
        Tree[Node] = Unite(Tree[Left], Tree[Right]);
    }
 
    public : void Build(const vector <type>& a)
    {
        Clear();
        n = a.size();
        Build(a, 1, 0, n - 1);
    }
 
    private : void Build(const vector <type>& a, int Node, int L, int R)
    {
        Tree[Node] = E;
        if(L == R)  return void(Tree[Node] = a[L]);
 
        Build(a, Left, L, Mid);
        Build(a, Right, Mid + 1, R);
 
        Merge(Node);
    }
 
    public : void Update(int i, type x)
    {
        if(0 > i || i >= n) return ;
        Update(i, x, 1, 0, n - 1);
    }
 
    private : void Update(int i, type x, int Node, int L, int R)
    {
        if(L == R)          return void(Tree[Node] = x);    /// Check This
 
        if(i <= Mid)    Update(i, x, Left, L, Mid);
        else            Update(i, x, Right, Mid + 1, R);
 
        Merge(Node);
    }
 
    public : type Query(int i, int j)
    {
        if(i < 0)   i = 0;
        if(j >= n)  j = n - 1;
        if(n <= 0 || i > j) return E;
        return Query(i, j, 1, 0, n - 1);
    }
 
    private : type Query(int i, int j, int Node, int L, int R)
    {
        if(j < L || R < i)      return E;
        if(i <= L && R <= j)    return Tree[Node];
 
        return Unite(Query(i, j, Left, L, Mid), Query(i, j, Right, Mid + 1, R));
    }
 
    private : void Clear()
    {
        for(int Node = 0; Node <= 4 * n; Node++)
            Tree[Node] = E;
        n = 0;
    }
 
    #undef Mid
    #undef Left
    #undef Right
};
SegmentTreeNonLazy<ii> st ;
vector<ii> a ;
int n ,p ;
int dfs(int l , int r) {
	if(l >= r) return 0 ;

	auto [mn, idx] = st.Query(l,r) ;
	int left = idx , right = idx ;
	while(left >= l && a[left].first % mn == 0) left-- ;
	while(right <= r && a[right].first % mn == 0) right++ ;
	left++ ;
	right-- ;

	int ans = (right-left) * min(p, mn) ;
	if(left < idx) ans += dfs(l,left) ;
	else if(idx-1 >= l) ans += dfs(l,idx-1) + p ;
	if(idx < right) ans += dfs(right, r) ;
	else if(idx+1 <= r) ans += dfs(idx+1, r) + p ;
	return ans ;
}

void solve(){
	cin >> n >> p ;
	a.resize(n) ;
	st.n = n ;
	for(auto& x : a) cin >> x.ff ;
	forn(i,n) a[i].ss = i ;
	st.Build(a) ;
	cout << dfs(0,n-1) << endl ;
}


int32_t main(){
    FAST_IO ;
    int t = 1 ;
    cin >> t ;
    while(t--){
        solve() ;
    }
}

```