You are given an array $a$ of $n$ ($n \geq 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}, \dots, a_{j}) = min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$, then there is an edge of weight $min(a_i, a_{i+1}, a_{i+2}, \dots, 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, \ldots)$ denotes the greatest common divisor (GCD) 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 of this graph.


-----Input-----

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

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

The second line contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($1 \leq a_i \leq 10^9$).

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


-----Output-----

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


-----Examples-----

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

For test case 2

For test case 3

For test case 4

Difficulty: HARD
Tags: Graph algorithms

Constructive algorithms

Sorting

Greedy algorithms

Number theory

Spanning trees
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import random
import collections
import string
import math
import copy
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
mo = int(1000000000.0 + 7)

def exgcd(a, b):
	if not b:
		return (1, 0)
	(y, x) = exgcd(b, a % b)
	y -= a // b * x
	return (x, y)

def getinv(a, m):
	(x, y) = exgcd(a, m)
	return -1 if x == 1 else x % m

def comb(n, b):
	res = 1
	b = min(b, n - b)
	for i in range(b):
		res = res * (n - i) * getinv(i + 1, mo) % mo
	return res % mo

def quickpower(a, n):
	res = 1
	while n:
		if n & 1:
			res = res * a % mo
		n >>= 1
		a = a * a % mo
	return res

def dis(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def getpref(x):
	if x > 1:
		return x * (x - 1) >> 1
	else:
		return 0

def orafli(upp):
	primes = []
	marked = [False for i in range(upp + 3)]
	prvs = [i for i in range(upp + 3)]
	for i in range(2, upp):
		if not marked[i]:
			primes.append(i)
		for j in primes:
			if i * j >= upp:
				break
			marked[i * j] = True
			prvs[i * j] = j
			if i % j == 0:
				break
	return (primes, prvs)

def lower_ord(c: str) -> int:
	return ord(c) - 97

def upper_ord(c: str) -> int:
	return ord(c) - 65

def read_list():
	return [int(i) for i in input().split()]

def read_int():
	s = input().split()
	if len(s) == 1:
		return int(s[0])
	else:
		return map(int, s)

def ask(s):
	print(f'? {s}', flush=True)

def answer(s):
	print(f'{s}', flush=True)
import traceback

def solve():
	(n, p) = read_int()
	lsorce = read_list()
	li = [(int(i), p) for (p, i) in enumerate(lsorce)]
	li.sort()
	vis = [False for i in li]
	ans = 0
	ato = n - 1
	for (val, pid) in li:
		if val >= p:
			break
		else:
			if vis[pid]:
				continue
			ll = pid
			rr = pid
			while ll < len(lsorce) - 1 and (not vis[ll]) and (lsorce[ll + 1] % val == 0):
				ll += 1
			while rr >= 1 and (not vis[rr]) and (lsorce[rr - 1] % val == 0):
				rr -= 1
			for ppp in range(rr, ll + 1):
				vis[ppp] = True
			ctr = ll - rr + 1
			ato -= ctr - 1
			ans += val * (ctr - 1)
	ans += ato * p
	print(ans)
t = int(input())
for ti in range(t):
	solve()


from sys import stdin
f = stdin
t = int(f.readline())

def solve(n, p, a):
	fathers = [i for i in range(n)]

	def getparent(a):
		if fathers[a] == a:
			return a
		father = getparent(fathers[a])
		fathers[a] = father
		return father

	def sameset(a, b):
		return getparent(a) == getparent(b)

	def uniset(a, b):
		fathers[a] = b
	paths = []
	for i in range(n):
		if a[i] < p:
			for bi in range(i - 1, 0, -1):
				if a[bi] % a[i] != 0:
					break
				if a[bi] < a[i]:
					break
				else:
					paths.append((bi, i, a[i]))
			for bi in range(i + 1, n, +1):
				if a[bi] % a[i] != 0:
					break
				if a[bi] < a[i]:
					break
				else:
					paths.append((bi, i, a[i]))
	paths.sort()
	sorted_paths = paths
	u = 0
	we = 0
	found = 0
	for i in range(n - 1):
		if u >= len(sorted_paths):
			break
		while True:
			if u >= len(sorted_paths):
				break
			current_path = sorted_paths[u]
			if not sameset(current_path[0], current_path[1]):
				uniset(current_path[0], current_path[1])
				we += current_path[2]
				found += 1
				u += 1
				break
			u += 1
	we += p * (n - found - 1)
	return we

def readlinesasint(n: int, file):
	buffer = []
	nums = []
	for i in range(n):
		char = file.read(1)
		while char not in '\r\n\t ':
			buffer.append(char)
			char = file.read(1)
		nums.append(int(''.join(buffer)))
		buffer = []
	return nums

def new_solve(n, p, a):
	sorted_a = sorted(enumerate(a), key=lambda x: x[1])
	is_connected_to_neighbour = [False for i in range(n - 1)]
	ret_val = 0
	for (index, value) in sorted_a:
		if value >= p:
			break
		i = index - 1
		while i >= 0:
			if a[i] % a[index] == 0:
				if is_connected_to_neighbour[i]:
					i -= 1
					break
					continue
				else:
					is_connected_to_neighbour[i] = True
					ret_val += a[index]
			else:
				break
			i -= 1
		i = index + 1
		while i < n:
			if a[i] % a[index] == 0:
				if is_connected_to_neighbour[i - 1]:
					i += 1
					break
					continue
				else:
					is_connected_to_neighbour[i - 1] = True
					ret_val += a[index]
			else:
				break
			i += 1
	for i in range(len(is_connected_to_neighbour)):
		if not is_connected_to_neighbour[i]:
			ret_val += p
	return ret_val
for i in range(t):
	(n, p) = map(int, f.readline().split())
	a = readlinesasint(n, f)
	print(new_solve(n, p, a))


def find(x):
	while par[x] != x:
		x = par[x]
	return x

def union(x, y):
	if rank[x] > rank[y]:
		par[y] = x
	elif rank[y] > rank[x]:
		par[x] = y
	else:
		par[x] = y
		rank[y] += 1
T = int(input())
for _ in range(T):
	(n, p) = map(int, input().split())
	A = list(map(int, input().split()))
	s = [[A[i], i] for i in range(n)]
	s.sort()
	vis = [0 for i in range(n)]
	par = [i for i in range(n)]
	rank = [0 for i in range(n)]
	ans = p * (n - 1)
	for i in range(n - 1):
		(val, ind) = s[i]
		if val >= p:
			break
		vis[ind] = 1
		for j in range(ind - 1, -1, -1):
			if A[j] % val != 0:
				break
			(x, y) = (find(ind), find(j))
			if x == y:
				break
			vis[j] = 1
			union(x, y)
			ans = ans + (val - p)
		for j in range(ind + 1, n):
			if A[j] % val != 0:
				break
			(x, y) = (find(ind), find(j))
			if x == y:
				break
			vis[j] = 1
			union(x, y)
			ans = ans + (val - p)
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = 10 ** 16
md = 10 ** 9 + 7

class UnionFind:

	def __init__(self, n):
		self.state = [-1] * n
		self.size_table = [1] * n
		self.cnt = n

	def root(self, u):
		stack = []
		while self.state[u] >= 0:
			stack.append(u)
			u = self.state[u]
		for v in stack:
			self.state[v] = u
		return u

	def merge(self, u, v):
		u = self.root(u)
		v = self.root(v)
		if u == v:
			return
		du = -self.state[u]
		dv = -self.state[v]
		if du < dv:
			(u, v) = (v, u)
		if du == dv:
			self.state[u] -= 1
		self.state[v] = u
		self.cnt -= 1
		self.size_table[u] += self.size_table[v]
		return

	def same(self, u, v):
		return self.root(u) == self.root(v)

	def size(self, u):
		return self.size_table[self.root(u)]
for _ in range(II()):
	(n, p) = LI()
	aa = LI()
	ai = [(a, i) for (i, a) in enumerate(aa)]
	ai.sort(key=lambda x: x[0])
	uf = UnionFind(n)
	ans = 0
	fin = [False] * n
	for (a, i) in ai:
		if a >= p:
			break
		if fin[i]:
			continue
		for j in range(i - 1, -1, -1):
			if aa[j] % a:
				break
			if uf.same(i, j):
				break
			ans += a
			uf.merge(i, j)
			fin[j] = True
		for j in range(i + 1, n):
			if aa[j] % a:
				break
			if uf.same(i, j):
				break
			ans += a
			uf.merge(i, j)
			fin[j] = True
	ans += (uf.cnt - 1) * p
	print(ans)


for t in range(int(input())):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	res = [p] * (n - 1)
	c = a[0]
	for i in range(1, n):
		if a[i] % c == 0:
			res[i - 1] = min(c, res[i - 1])
		else:
			c = a[i]
	c = a[n - 1]
	for i in range(n - 2, -1, -1):
		if a[i] % c == 0:
			res[i] = min(c, res[i])
		else:
			c = a[i]
	print(sum(res))


import heapq
import sys
input = sys.stdin.readline

def get_root(s):
	v = []
	while not s == root[s]:
		v.append(s)
		s = root[s]
	for i in v:
		root[i] = s
	return s

def unite(s, t):
	root_s = get_root(s)
	root_t = get_root(t)
	if not root_s == root_t:
		if rank[s] == rank[t]:
			root[root_t] = root_s
			rank[root_s] += 1
		elif rank[s] > rank[t]:
			root[root_t] = root_s
		else:
			root[root_s] = root_t

def same(s, t):
	if get_root(s) == get_root(t):
		return True
	else:
		return False
t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	end = [0] * n
	root = [i for i in range(n)]
	rank = [1 for _ in range(n)]
	ans = p * (n - 1)
	h = []
	for i in range(n):
		heapq.heappush(h, (a[i], i))
	while h:
		(ai, i) = heapq.heappop(h)
		if ai >= p:
			break
		for j in range(i + 1, n):
			if end[j]:
				break
			if not a[j] % ai:
				if not same(i, j):
					unite(i, j)
					end[j] = 1
					ans += ai - p
			else:
				end[j - 1] = 0
				break
		for j in range(i - 1, -1, -1):
			if end[j]:
				break
			if not a[j] % ai:
				if not same(i, j):
					unite(i, j)
					end[j] = 1
					ans += ai - p
			else:
				end[j + 1] = 0
				break
		end[i] = 1
	print(ans)


import sys
input = sys.stdin.readline
output = sys.stdout.write

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	t = inp()
	for _ in range(0, t):
		[n, p] = inlt()
		a = inlt()
		solve(n, p, a)

def dsu_init(n):
	return [i for i in range(0, n)]

def dsu_head(u, dsu):
	if u == dsu[u]:
		return u
	else:
		dsu[u] = dsu_head(dsu[u], dsu)
		return dsu[u]

def dsu_union(u, v, dsu):
	u_head = dsu_head(u, dsu)
	v_head = dsu_head(v, dsu)
	dsu[u_head] = v_head
	return v_head

def solve(n, p, a):
	dsu = dsu_init(n)
	weights = [None] * (n + 1)
	for i in range(0, n):
		weights[i] = [a[i], i]
	weights[n] = [p, n]
	weights.sort()
	mark = [False] * n
	tot_weight = 0
	edge_cnt = 0

	def pick_window(wi):
		wl = wi
		for i in range(wi, -1, -1):
			if a[i] % a[wi] != 0:
				break
			else:
				wl = i
				if mark[i]:
					break
		wr = wi
		for i in range(wi, n, 1):
			if a[i] % a[wi] != 0:
				break
			else:
				wr = i
				if mark[i]:
					break
		return [wl, wr]

	def adj_connect():
		c = 0
		for i in range(0, n - 1):
			if dsu_head(i, dsu) != dsu_head(i + 1, dsu):
				dsu_union(i, i + 1, dsu)
				c = c + 1
		return c

	def window_connect(wl, wr, wi):
		for i in range(wl, wr + 1):
			mark[i] = True
			if i != wi:
				dsu_union(i, wi, dsu)
		return wr - wl
	for [w, wi] in weights:
		c = 0
		if wi == n:
			c = adj_connect()
		else:
			[wl, wr] = pick_window(wi)
			c = window_connect(wl, wr, wi)
		edge_cnt = edge_cnt + c
		tot_weight = tot_weight + c * w
		if edge_cnt == n - 1:
			break
	output(str(tot_weight))
	output('\n')
main()


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(test,) = Neo()
for _ in range(test):
	(n, p) = Neo()
	A = Neo()
	vis = set()
	Ans = [p] * (n - 1)
	for (i, val) in enumerate(A):
		if i not in vis:
			for j in range(i - 1, -1, -1):
				if A[j] % val == 0:
					Ans[j] = min(Ans[j], val)
					vis.add(j)
				else:
					break
			for j in range(i + 1, n):
				if A[j] % val == 0:
					Ans[j - 1] = min(Ans[j - 1], val)
					vis.add(j)
				else:
					break
	print(sum(Ans))


from collections import defaultdict

class UnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for _ in range(N)]

	def find(self, x):
		if self.parent[x] == x:
			return x
		else:
			return self.find(self.parent[x])

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		if px == py:
			return
		if self.size[px] < self.size[py]:
			self.parent[px] = py
			self.size[py] += self.size[px]
		else:
			self.parent[py] = px
			self.size[px] += self.size[py]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def connectedNum(self, x):
		return self.size[self.find(x)]

	def is_connected(self):
		return self.connectedNum(0) == len(self.parent)

	def conpomentNum(self):
		par_set = set()
		for p in self.parent:
			par_set.add(self.find(p))
		return len(par_set)

def solve():
	(N, P) = map(int, input().split())
	L = list(map(int, input().split()))
	edges = defaultdict(lambda : 10 ** 9 + 7)
	for i in range(N - 1):
		edges[i, i + 1] = P
	tmp_gcd = 10 ** 9 + 7
	min_idx = None
	for (i, l) in enumerate(L):
		if l % tmp_gcd == 0:
			edges[min_idx, i] = min(edges[min_idx, i], tmp_gcd)
		else:
			tmp_gcd = l
			min_idx = i
	tmp_gcd = 10 ** 9 + 7
	min_idx = None
	for (i, l) in zip(reversed(range(N)), reversed(L)):
		if l % tmp_gcd == 0:
			edges[i, min_idx] = min(edges[i, min_idx], tmp_gcd)
		else:
			tmp_gcd = l
			min_idx = i
	Un = UnionFind(N)
	ans = 0
	Q = []
	for (key, val) in edges.items():
		Q.append((val, key[0], key[1]))
	Q = sorted(Q)
	for (cost, node1, node2) in Q:
		if Un.same(node1, node2):
			continue
		else:
			Un.union(node1, node2)
			ans += cost
	print(ans)
T = int(input())
for _ in range(T):
	solve()


import sys
from sys import stdin

def uf_find(n, p):
	ufl = []
	while p[n] != n:
		ufl.append(n)
		n = p[n]
	for i in ufl:
		p[i] = n
	return n

def uf_union(a, b, p, rank):
	ap = uf_find(a, p)
	bp = uf_find(b, p)
	if ap == bp:
		return True
	else:
		if rank[ap] > rank[bp]:
			p[bp] = ap
		elif rank[ap] < rank[bp]:
			p[ap] = bp
		else:
			p[bp] = ap
			rank[ap] += 1
		return False
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	(N, P) = map(int, stdin.readline().split())
	a = list(map(int, stdin.readline().split()))
	ai = [(a[i], i) for i in range(N)]
	ai.sort()
	p = [i for i in range(N)]
	rank = [0] * N
	ans = 0
	rem = N - 1
	for (na, ni) in ai:
		if na > P:
			break
		for j in range(ni - 1, -1, -1):
			if a[j] % na != 0:
				break
			if uf_union(ni, j, p, rank):
				break
			else:
				ans += na
				rem -= 1
		for j in range(ni + 1, N):
			if a[j] % na != 0:
				break
			if uf_union(ni, j, p, rank):
				break
			else:
				ans += na
				rem -= 1
	ANS.append(str(ans + rem * P))
print('\n'.join(ANS))


from sys import stdin, stdout
import collections, heapq, bisect, math
input = stdin.readline

def rint():
	return int(input())

def rstr():
	return input().strip()

def rlstr():
	return list(input().strip().split())

def rlint():
	return list(map(int, input().split()))

def main():
	(n, p) = rlint()
	a = rlint()
	b = [p] * (n - 1)
	c = a[0]
	for i in range(1, n):
		if a[i] % c == 0:
			b[i - 1] = min(b[i - 1], c)
		else:
			c = a[i]
	c = a[-1]
	for i in range(n - 2, -1, -1):
		if a[i] % c == 0:
			b[i] = min(b[i], c)
		else:
			c = a[i]
	print(sum(b))
for _ in range(rint()):
	main()


from sys import stdin
from math import gcd
t = int(stdin.readline())
for _ in range(t):
	(n, p) = map(int, stdin.readline().split())
	arr = [1000000007] + list(map(int, stdin.readline().split())) + [1000000007]
	paths = [p] * (n - 1)
	if 1 in arr:
		print(n - 1)
		continue
	i = 1
	while i <= n:
		j = i + 1
		while arr[i] <= arr[j] and gcd(arr[i], arr[j]) == arr[i]:
			paths[j - 2] = min(paths[j - 2], arr[i])
			j += 1
		i = j
	i = n
	while i >= 1:
		j = i - 1
		while arr[i] <= arr[j] and gcd(arr[i], arr[j]) == arr[i]:
			paths[j - 1] = min(paths[j - 1], arr[i])
			j -= 1
		i = j
	print(sum(paths))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
for _ in range(inp()):
	(n, p) = inpl()
	a = inpl()
	q = []
	for (i, x) in enumerate(a):
		heappush(q, (x, i))
	seen = set()
	res = 0
	while q:
		(cost, i) = heappop(q)
		if i in seen:
			continue
		if cost >= p:
			break
		for j in range(i, n - 1):
			if j in seen or a[j + 1] % cost != 0:
				break
			res += cost
			seen.add(j)
		for j in range(i - 1, -1, -1):
			if j in seen or a[j] % cost != 0:
				break
			res += cost
			seen.add(j)
	res += (n - 1 - len(seen)) * p
	print(res)


from sys import stdin, stdout
import collections, heapq, bisect, math
input = stdin.readline

def rint():
	return int(input())

def rstr():
	return input().strip()

def rlstr():
	return list(input().strip().split())

def rlint():
	return list(map(int, input().split()))

def main():
	(n, p) = rlint()
	a = rlint()
	d = []
	connected = [False] * n
	for i in range(n):
		d.append((a[i], i))
	d.sort()
	res = 0
	for (cur, t) in d:
		if cur >= p:
			break
		i = t
		while i > 0:
			if connected[i - 1]:
				break
			if a[i - 1] % cur == 0:
				connected[i - 1] = True
				res += cur
				i -= 1
			else:
				break
		i = t
		while i < n - 1:
			if connected[i]:
				break
			if a[i + 1] % cur == 0:
				connected[i] = True
				res += cur
				i += 1
			else:
				break
	for i in range(n - 1):
		if not connected[i]:
			res += p
	print(res)
for _ in range(rint()):
	main()


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations
from bisect import bisect_right

def main():
	(n, p) = map(int, input().split())
	arr = list(map(int, input().split()))
	brr = []
	for i in range(n):
		brr.append((arr[i], i))
	brr.sort()
	brr.reverse()
	connected = [0] * n
	ans = 0
	for i in range(n):
		(val, idx) = brr.pop()
		if val > p:
			break
		if connected[idx]:
			continue
		for i in range(idx - 1, -1, -1):
			if connected[i] == 0 and arr[i] % val == 0:
				ans += val
				connected[i] = 1
			else:
				break
		for i in range(idx + 1, n, +1):
			if connected[i - 1] == 0 and arr[i] % val == 0:
				ans += val
				connected[i - 1] = 1
			else:
				break
	sm = sum(connected)
	print(ans + p * (n - 1 - sm))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([arr[i], i])
	l.sort()
	vis = set()
	ans = 0
	for i in l:
		ele = i[0]
		ind = i[1]
		if ele > p:
			break
		if ind in vis:
			continue
		while ind > 0:
			if ind - 1 in vis:
				break
			if arr[ind - 1] % ele == 0:
				vis.add(ind - 1)
				ans += ele
			else:
				break
			ind -= 1
		ind = i[1]
		while ind < n - 1:
			if ind in vis:
				break
			if arr[ind + 1] % ele == 0:
				vis.add(ind)
				ans += ele
			else:
				break
			ind += 1
	for i in range(n - 1):
		if i not in vis:
			ans += p
	print(ans)


test = int(input())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for t in range(test):
	(n, p) = [int(i) for i in input().split(' ')]
	a = [int(i) for i in input().split(' ')]
	bo = [-1 for i in range(n - 1)]
	b = []
	c = 0
	for e in a:
		b.append([e, c])
		c += 1
	b.sort()
	for e in b:
		if e[0] >= p:
			break
		ix = e[1]
		bi = ix - 1
		fi = ix + 1
		while bi >= 0 and bo[bi] == -1 and (gcd(a[ix], a[bi]) == a[ix]):
			bo[bi] = a[ix]
			bi -= 1
		while fi < n and bo[fi - 1] == -1 and (gcd(a[ix], a[fi]) == a[ix]):
			bo[fi - 1] = a[ix]
			fi += 1
	for i in range(0, n - 1):
		if bo[i] == -1:
			bo[i] = p
	print(sum(bo))


import io
import os
from heapq import heappop, heappush
from collections import Counter, defaultdict, deque
from math import gcd
from typing import Union

class RangeQuery:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, start, stop):
		depth = (stop - start).bit_length() - 1
		return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])

	def __getitem__(self, idx):
		return self._data[0][idx]

def prim(n, getAdj):
	total_weight = 0
	(selected, min_e) = ([False] * n, [[float('inf'), -1] for _ in range(n)])
	mst_edges = []
	min_e[0][0] = 0
	for i in range(n):
		v = -1
		for j in range(n):
			if not selected[j] and (v == -1 or min_e[j][0] < min_e[v][0]):
				v = j
		if min_e[v][0] == float('inf'):
			return (None, None)
		selected[v] = True
		total_weight += min_e[v][0]
		if min_e[v][1] != -1:
			mst_edges.append((v, min_e[v][1]))
		for (to, w) in getAdj(v):
			if w < min_e[to][0]:
				min_e[to] = [w, v]
	return total_weight

def solve1(N, P, A):
	rangeMin = RangeQuery(A, min)
	rangeGcd = RangeQuery(A, gcd)
	graph = [[] for i in range(N)]
	for i in range(N):
		for j in range(i + 1, N):
			g = rangeGcd.query(i, j + 1)
			m = rangeMin.query(i, j + 1)
			if g == m:
				graph[i].append((j, m))
				graph[j].append((i, m))
		if i + 1 < N:
			graph[i].append((i + 1, P))
			graph[i + 1].append((i, P))
	return prim(N, lambda i: graph[i])

class UnionFind:

	def __init__(self, N):
		self.p = [-1 for i in range(N)]

	def find(self, i):
		if self.p[i] >= 0:
			self.p[i] = self.find(self.p[i])
			return self.p[i]
		else:
			return i

	def union(self, i, j):
		root1 = self.find(j)
		root2 = self.find(i)
		if root1 == root2:
			return
		size1 = -self.p[root1]
		size2 = -self.p[root2]
		if size1 < size2:
			self.p[root1] = root2
			self.p[root2] = -(size1 + size2)
		else:
			self.p[root2] = root1
			self.p[root1] = -(size1 + size2)

	def getComponentSize(self, i):
		return -self.p[self.find(i)]

def solve(N, P, A):
	cost = 0
	uf = UnionFind(N)
	order = sorted(range(N), key=lambda i: A[i])
	for i in order:
		m = A[i]
		if m >= P:
			break
		j = i - 1
		while j >= 0 and gcd(A[j], m) == m and (A[j] >= m):
			if uf.getComponentSize(j) != 1:
				j -= 1
				break
			j -= 1
		k = i + 1
		while k < N and gcd(A[k], m) == m and (A[k] >= m):
			if uf.getComponentSize(k) != 1:
				k += 1
				break
			k += 1
		j += 1
		if k - j == 1:
			continue
		for ii in range(j, k):
			if i != ii:
				if uf.find(i) != uf.find(ii):
					uf.union(i, ii)
					cost += m
	for i in range(N - 1):
		j = i + 1
		if uf.find(i) != uf.find(j):
			uf.union(i, j)
			cost += P
	return cost
if False:
	N = 2 * 10 ** 5
	solve(N, 1, [10 ** 9] * N)
	exit()
DEBUG = False
if DEBUG:
	import random
	random.seed(0)
	for _ in range(1000000):
		N = random.randint(1, 10)
		P = random.randint(1, 10)
		A = [random.randint(1, 10) for i in range(N)]
		print('tc' + str(_), N, P, A)
		ans1 = solve1(N, P, A)
		ans = solve(N, P, A)
		print(ans, ans1)
		assert ans1 == ans
	exit()
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, P) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	ans = solve(N, P, A)
	print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict
import heapq
t = int(input())
for _ in range(t):
	heap = []
	disjoint_sets = []
	set_id = dict()
	counted = 0
	ans = 0
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		heapq.heappush(heap, (a[i], i))
	while heap and counted < n - 1:
		(min_edge, curr_idx) = heapq.heappop(heap)
		if min_edge >= p:
			break
		idx = curr_idx
		while idx > 0:
			u = idx
			v = idx - 1
			if a[v] % min_edge != 0:
				break
			if set_id.get(u) != None and set_id.get(v) != None:
				if set_id[u] == set_id[v]:
					break
				else:
					disjoint_sets[set_id[u]].update(disjoint_sets[set_id[v]])
					for i in disjoint_sets[set_id[v]]:
						set_id[i] = set_id[u]
			elif set_id.get(u) != None:
				disjoint_sets[set_id[u]].add(v)
				set_id[v] = set_id[u]
			elif set_id.get(v) != None:
				disjoint_sets[set_id[v]].add(u)
				set_id[u] = set_id[v]
			else:
				set_id[u] = len(disjoint_sets)
				set_id[v] = len(disjoint_sets)
				disjoint_sets.append({u, v})
			ans += min_edge
			counted += 1
			idx -= 1
		idx = curr_idx
		while idx < n - 1:
			u = idx
			v = idx + 1
			if a[v] % min_edge != 0:
				break
			if set_id.get(u) != None and set_id.get(v) != None:
				if set_id[u] == set_id[v]:
					break
				else:
					disjoint_sets[set_id[u]].update(disjoint_sets[set_id[v]])
					for i in disjoint_sets[set_id[v]]:
						set_id[i] = set_id[u]
			elif set_id.get(u) != None:
				disjoint_sets[set_id[u]].add(v)
				set_id[v] = set_id[u]
			elif set_id.get(v) != None:
				disjoint_sets[set_id[v]].add(u)
				set_id[u] = set_id[v]
			else:
				set_id[u] = len(disjoint_sets)
				set_id[v] = len(disjoint_sets)
				disjoint_sets.append({u, v})
			ans += min_edge
			counted += 1
			idx += 1
	print(ans + (n - 1 - counted) * p)


from sys import stdin, stdout, setrecursionlimit
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log, log2
from random import seed, randint
from datetime import datetime
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
from collections import defaultdict as dd
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def def_value():
	return 0

def def_inf():
	return inf

def atoi(s):
	return ord(s) - ord('a')

def inc(s, n=1):
	return chr((ord(s) - ord('a') + n) % 26 + ord('a'))

def find(i):
	if parent[i] == -1:
		return i
	if parent[i] != -1:
		return find(parent[i])

def union(x, y):
	if rank[x] > rank[y]:
		parent[y] = x
	elif rank[y] > rank[x]:
		parent[x] = y
	else:
		parent[x] = y
		rank[y] += 1
for _ in range(iinp()):
	(n, p) = mp()
	a = lmp()
	aa = [[a[i], i] for i in range(n)]
	parent = [-1 for i in range(n)]
	rank = [0 for i in range(n)]
	aa.sort()
	sm = 0
	cnt = 0
	for i in range(n):
		if aa[i][0] >= p:
			break
		gd = aa[i][0]
		idx = aa[i][1]
		for j in range(idx - 1, -1, -1):
			if a[j] % gd == 0:
				x = find(idx)
				y = find(j)
				if y == x:
					break
				else:
					sm += gd
					cnt += 1
					union(x, y)
			else:
				break
		for j in range(idx + 1, n):
			if a[j] % gd == 0:
				x = find(idx)
				y = find(j)
				if y == x:
					break
				else:
					sm += gd
					cnt += 1
					union(x, y)
			else:
				break
	print(sm + p * (n - 1 - cnt))


import sys
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
	(n, p) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	cost = [0] * n
	mini = a[0]
	for i in range(1, n):
		if a[i] % mini == 0:
			mini = min(a[i], mini)
			cost[i] = min(mini, p)
		else:
			cost[i] = p
			mini = a[i]
	mini = a[-1]
	for i in range(n - 2, -1, -1):
		if a[i] % mini == 0:
			mini = min(a[i], mini)
			cost[i + 1] = min(mini, cost[i + 1])
		else:
			mini = a[i]
	print(sum(cost))


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [p] * (n - 1)
	curr = a[0]
	for i in range(1, n):
		if a[i] % curr == 0:
			b[i - 1] = min(curr, b[i - 1])
		else:
			curr = a[i]
	curr = a[n - 1]
	for i in range(n - 2, -1, -1):
		if a[i] % curr == 0:
			b[i] = min(curr, b[i])
		else:
			curr = a[i]
	print(sum(b))


class UnionFind:

	def __init__(self, n):
		self.Id = list(range(n + 1))
		self.sz = [1] * (n + 1)

	def find(self, node):
		root = node
		while root != self.Id[root]:
			root = self.Id[root]
		while node != root:
			nxt = self.Id[node]
			self.Id[node] = root
			node = nxt
		return root

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.sz[pu] <= self.sz[pv]:
			self.Id[pu] = pv
			self.sz[pv] += self.sz[pu]
		else:
			self.Id[pv] = pu
			self.sz[pu] += self.sz[pv]
		return True

def solve(A, n, p):
	edg = []
	for i in range(1, n):
		edg.append((p, i, i + 1))
	(pel, pind) = (10 ** 9 + 10, 1)
	for (i, it) in enumerate(A):
		if it % pel == 0:
			edg.append((pel, pind, i + 1))
		else:
			(pel, pind) = (it, i + 1)
	(pel, pind) = (10 ** 9 + 10, n)
	i = n
	for it in A[-1::-1]:
		if it % pel == 0:
			edg.append((pel, i, pind))
		else:
			(pel, pind) = (it, i)
		i -= 1
	edg.sort()
	dsu = UnionFind(n)
	ans = 0
	for (w, u, v) in edg:
		if dsu.union(u, v):
			ans += w
	return ans
for case in range(int(input())):
	(n, p) = map(int, input().split())
	A = list(map(int, input().split()))
	ans = solve(A, n, p)
	print(ans)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	Answer = [p] * (n - 1)
	c = a[0]
	for i in range(1, n):
		if a[i] % c < 1:
			Answer[i - 1] = min(c, Answer[i - 1])
		else:
			c = a[i]
	c = a[n - 1]
	for i in range(n - 2, -1, -1):
		if a[i] % c < 1:
			Answer[i] = min(c, Answer[i])
		else:
			c = a[i]
	print(sum(Answer))


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(n, p) = map(int, input().split())
		a = list(map(int, input().split()))
		b = sorted(zip(a, list(range(n))), key=lambda x: x[0])
		(ans, v) = (0, [0] * n)
		for i in b:
			if i[0] >= p:
				break
			for j in range(i[1], n - 1, 1):
				if v[j] or a[j + 1] % i[0]:
					break
				ans += i[0]
				v[j] = 1
			for j in range(i[1], 0, -1):
				if v[j - 1] or a[j - 1] % i[0]:
					break
				ans += i[0]
				v[j - 1] = 1
		print(ans + v[:-1].count(0) * p)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	for _ in range(int(input())):
		(n, p) = map(int, input().split())
		a = list(map(int, input().split()))
		b = [[a[i], i] for i in range(n)]
		b.sort()
		vis = [-1 for i in range(n)]
		c = n - 1
		ans = 0
		for i in b:
			if c == 0:
				break
			ind = i[1]
			if vis[i[1]] == -1 and i[0] < p:
				vis[i[1]] = i[0]
				ind = i[1] - 1
				while ind >= 0 and vis[ind] == -1 and (a[ind] % i[0] == 0) and c:
					vis[ind] = i[0]
					ind -= 1
					c -= 1
					ans += i[0]
				if ind >= 0 and vis[ind] != i[0] and (a[ind] % i[0] == 0) and c:
					c -= 1
					ans += i[0]
				ind = i[1] + 1
				while ind < n and vis[ind] == -1 and (a[ind] % i[0] == 0) and c:
					vis[ind] = i[0]
					ind += 1
					c -= 1
					ans += i[0]
				if ind < n and vis[ind] != i[0] and (a[ind] % i[0] == 0) and c:
					c -= 1
					ans += i[0]
		ans += p * c
		print(ans)
	return
main()


def I():
	return map(int, input().split())
(t,) = I()
r = range
for _ in r(t):
	(n, p) = I()
	a = (*I(),)
	b = [p] * (n - 1)
	c = a[0]
	for i in r(1, n):
		if a[i] % c:
			c = a[i]
		else:
			b[i - 1] = min(c, b[i - 1])
	c = a[n - 1]
	for i in r(n - 2, -1, -1):
		if a[i] % c:
			c = a[i]
		else:
			b[i] = min(c, b[i])
	print(sum(b))


from sys import stdin, stdout, maxsize
R = lambda : stdin.readline().strip()
RL = lambda f=None: list(map(f, R().split(' '))) if f else list(R().split(' '))
output = lambda x: stdout.write(str(x) + '\n')
output_list = lambda x: output(' '.join(map(str, x)))
for tc in range(int(R())):
	(n, p) = RL(int)
	a = RL(int)
	nodes = [[a[i], i] for i in range(n)]
	nodes.sort()
	visited = n * [False]
	ans = 0
	for node in nodes:
		(v, i) = node
		if v >= p:
			break
		while i > 0:
			if visited[i - 1]:
				break
			if a[i - 1] % v == 0:
				ans += v
				visited[i - 1] = True
				i -= 1
			else:
				break
		i = node[1]
		while i < n - 1:
			if visited[i]:
				break
			if a[i + 1] % v == 0:
				ans += v
				visited[i] = True
				i += 1
			else:
				break
	ans += sum([0 if visited[i] else p for i in range(n - 1)])
	print(ans)


import sys, os, io
input = sys.stdin.readline
for _ in range(int(input())):
	(n, p) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	cost = [0] * n
	mini = 10 ** 10
	for i in range(1, n):
		if a[i] % mini == 0 or a[i] % a[i - 1] == 0:
			mini = min(a[i], a[i - 1], mini)
			cost[i] = min(mini, p)
		else:
			cost[i] = p
			mini = 10 ** 10
	mini = 10 ** 10
	for i in range(n - 2, -1, -1):
		if a[i] % mini == 0 or a[i] % a[i + 1] == 0:
			mini = min(a[i], a[i + 1], mini)
			cost[i + 1] = min(mini, cost[i + 1])
		else:
			mini = 10 ** 10
	print(sum(cost))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def modInverse(b):
	g = gcd(b, mod)
	if g != 1:
		return -1
	else:
		return pow(b, mod - 2, mod)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

class RangeQuery:

	def __init__(self, data, func=min):
		self.func = func
		self._data = _data = [list(data)]
		(i, n) = (1, len(_data[0]))
		while 2 * i <= n:
			prev = _data[-1]
			_data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
			i <<= 1

	def query(self, start, stop):
		depth = (stop - start).bit_length() - 1
		return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])

	def __getitem__(self, idx):
		return self._data[0][idx]

def solve(case):
	(n, p) = sep()
	a = lis()
	prev = 0
	left = [a[prev]]
	for i in range(1, n):
		if a[i] % left[i - 1] == 0:
			left.append(left[i - 1])
		else:
			left.append(a[i])
	right = [a[n - 1]] * n
	for i in range(n - 2, -1, -1):
		if a[i] % right[i + 1] == 0:
			right[i] = right[i + 1]
		else:
			right[i] = a[i]
	ans = 0
	for i in range(1, n):
		curr = p
		if left[i] == left[i - 1]:
			curr = min(curr, left[i])
		if right[i] == right[i - 1]:
			curr = min(curr, right[i])
		ans += curr
	print(ans)
testcase(int(inp()))


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		self.parent[self.find(b)] = self.find(a)

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		(n, p) = readIntArr()
		a = readIntArr()
		uf = UnionFind(n)
		b = [[i, x] for (i, x) in enumerate(a)]
		b.sort(key=lambda x: x[1])
		ans = 0
		for (i, x) in b:
			if x >= p:
				break
			l = i - 1
			while l >= 0 and gcd(a[l], a[i]) == a[i]:
				if uf.find(l) == uf.find(i):
					break
				else:
					uf.union(l, i)
					ans += a[i]
					l -= 1
			r = i + 1
			while r < n and gcd(a[i], a[r]) == a[i]:
				if uf.find(i) == uf.find(r):
					break
				else:
					uf.union(i, r)
					ans += a[i]
					r += 1
		for i in range(1, n):
			if uf.find(i) != uf.find(i - 1):
				uf.union(i, i - 1)
				ans += p
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
pr = lambda x: x

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	for _ in range(int(input())):
		(n, p) = aj()
		A = aj()
		w = [p] * (n - 1)
		B = [(A[i], i) for i in range(n)]
		B.sort()
		for (x, i) in B:
			for j in range(i - 1, -1, -1):
				if A[j] % x == 0 and x < w[j]:
					w[j] = x
				else:
					break
			for j in range(i + 1, n):
				if A[j] % x == 0 and x < w[j - 1]:
					w[j - 1] = x
				else:
					break
		print(sum(w))
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	from aj import *
except:
	pass
solve()


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict, deque
from io import BytesIO, IOBase
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def solve_a():
	(n, k) = get_ints()
	q = deque(list(range(1, n + 1)))
	if k > (n - 1) // 2:
		return False
	a = [0] * n
	for i in range(k):
		a[2 * i + 1] = q.pop()
	for i in range(n):
		if a[i] == 0:
			a[i] = q.popleft()
	return a

def solve_b():
	n = get_int()
	a = get_ints()
	A = Counter(a)
	M = 10 ** 9 + 7
	m = min(a)
	for x in a:
		if x & m != m:
			return 0
	if A[m] < 2:
		return 0
	else:
		ans = A[m] * (A[m] - 1) % M
		for i in range(1, n - 1):
			ans *= i
			ans %= M
		return ans

def preprocess_c(m, MOD):
	dp = []
	for i in range(m + 11):
		if i < 10:
			dp.append(1)
		else:
			dp.append(dp[-10] + dp[-9] % MOD)
	return dp

def solve_c(dp):
	(n, m) = get_ints()
	MOD = 10 ** 9 + 7
	s = str(n)
	ans = 0
	for char in s:
		x = int(char)
		ans += dp[m + x]
		ans %= MOD
	return ans

class DSU:

	def __init__(self, nodes, recursive=True, choose_join=True):
		self.p = [i for i in range(nodes)]
		self.r = [0 for i in range(nodes)]
		self.s = [1 for i in range(nodes)]
		self.recursive = recursive
		self.choose_join = choose_join

	def _get_recursive(self, u):
		if u != self.p[u]:
			self.p[u] = self.get(self.p[u])
		return self.p[u]

	def _get_nonrecursive(self, u):
		v = self.p[u]
		while v != self.p[v]:
			v = self.p[v]
		while u != v:
			(u, self.p[u]) = (self.p[u], v)
		return v

	def get(self, u):
		if self.recursive:
			return self._get_recursive(u)
		else:
			return self._get_nonrecursive(u)

	def union(self, u, v):
		u = self.get(u)
		v = self.get(v)
		if u != v:
			if self.r[u] > self.r[v] and self.choose_join:
				(u, v) = (v, u)
			self.p[u] = v
			if self.r[u] == self.r[v]:
				self.r[v] += 1
			self.s[v] += self.s[u]

def solve_d():
	(n, p) = get_ints()
	a = get_ints()
	a_enum = [(x, i) for (i, x) in enumerate(a)]
	a_enum.sort()
	dsu = DSU(n)
	ans = 0
	vis = [False for _ in range(n)]
	for (x, i) in a_enum:
		if x >= p:
			break
		if vis[i]:
			continue
		for j in range(i - 1, -1, -1):
			if a[j] % x != 0:
				break
			elif dsu.get(i) == dsu.get(j):
				break
			ans += x
			dsu.union(i, j)
			vis[j] = True
		for j in range(i + 1, n):
			if a[j] % x != 0:
				break
			if dsu.get(i) == dsu.get(j):
				break
			ans += x
			dsu.union(i, j)
			vis[j] = True
	cnt = 0
	for i in range(n):
		if dsu.get(i) == i:
			cnt += 1
	ans += (cnt - 1) * p
	return ans
t = get_int()
ans = []
for _ in range(t):
	ans.append(solve_d())
print(*ans)


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	(n, k) = R()
	(*a,) = R()
	v = [k] * (n - 1)
	mn = a[0]
	g = a[0]
	for i in range(n - 1):
		g = gcd(g, a[i + 1])
		if g == mn:
			v[i] = min(v[i], mn)
		else:
			g = a[i + 1]
			mn = a[i + 1]
	g = a[-1]
	mn = a[-1]
	for i in range(n - 1, 0, -1):
		g = gcd(g, a[i - 1])
		if g == mn:
			v[i - 1] = min(v[i - 1], mn)
		else:
			g = a[i - 1]
			mn = a[i - 1]
	print(sum(v))


from sys import stdin, stdout
input = stdin.readline

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	vals = []
	d = {}
	for i in range(n):
		vals.append((a[i], i))
		d[i] = a[i]
	vals = SortedList(vals)
	ok = []
	taken = set()
	while len(vals):
		p = vals[0]
		vals.remove(p)
		val = p[0]
		ind = p[1]
		taken.add(ind)
		org = ind
		a = b = org
		while 1:
			org -= 1
			if org < 0:
				a = 0
				break
			if d[org] % val != 0:
				a = org + 1
				break
			else:
				if org in taken:
					a = org
					break
				vals.remove((d[org], org))
				taken.add(org)
		while 1:
			ind += 1
			if ind == n:
				b = n - 1
				break
			if d[ind] % val != 0:
				b = ind - 1
				break
			else:
				if ind in taken:
					b = ind
					break
				vals.remove((d[ind], ind))
				taken.add(ind)
		ok.append((a, b, val))
	ok = sorted(ok)
	ans = min(ok[0][2], m) * (ok[0][1] - ok[0][0])
	last = ok[0][1]
	for i in ok[1:]:
		ans += (i[0] - last) * m
		ans += min(i[2], m) * (i[1] - i[0])
		last = i[1]
	print(ans)


from sys import stdin
input = stdin.readline
import math
mod = 10 ** 9 + 7
t = int(input())
for i in range(t):
	(n, p) = map(int, input().split())
	l = list(map(int, input().split()))
	s = []
	for i in range(n):
		s.append((l[i], i))
	s.sort()
	ans = 0
	x = [0] * n
	for i in s:
		(a, b) = (i[0], i[1])
		if a >= p:
			break
		else:
			j = b
			while j > 0 and l[j - 1] % a == 0:
				if j > 0 and x[j - 1]:
					break
				ans += a
				x[j - 1] = 1
				j -= 1
			j = b
			while j < n - 1 and l[j + 1] % a == 0:
				if j < n - 1 and x[j]:
					break
				ans += a
				x[j] = 1
				j += 1
	for i in x[:n - 1]:
		if i == 0:
			ans += p
	print(ans)


import sys
input = sys.stdin.readline
cas = int(input())
while cas:
	cas -= 1
	(n, p) = map(int, input().split())
	tt = list(map(int, input().split()))
	a = []
	vis = [0 for i in range(n)]
	for i in range(n):
		a.append([tt[i], i])
	a.sort()
	cnt = n - 1
	ans = 0
	for i in range(n):
		x = a[i][0]
		pos = a[i][1]
		if x >= p:
			break
		if vis[pos]:
			continue
		l = pos
		r = pos
		for j in range(pos - 1, -1, -1):
			if tt[j] % x:
				break
			l = j
			if vis[j]:
				break
			vis[j] = 1
		for j in range(pos + 1, n):
			if tt[j] % x:
				break
			r = j
			if vis[j]:
				break
			vis[j] = 1
		ans += (r - l) * x
		cnt -= r - l
	print(ans + cnt * p)


from math import gcd
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	total = [p] * (n - 1)
	curr = arr[0]
	for i in range(1, n):
		if arr[i] % curr == 0:
			total[i - 1] = min(total[i - 1], curr)
		else:
			curr = arr[i]
	curr = arr[n - 1]
	for i in range(n - 2, -1, -1):
		if arr[i] % curr == 0:
			total[i] = min(total[i], curr)
		else:
			curr = arr[i]
	print(sum(total))


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, p) = get_ints()
	a = get_array()
	isCon = [False] * n
	vals = []
	for i in range(n):
		vals.append([a[i], i])
	vals.sort()
	ans = 0
	for (cur_val, i) in vals:
		if cur_val >= p:
			break
		j = i
		while i:
			if isCon[i - 1]:
				break
			if a[i - 1] % cur_val == 0:
				ans += cur_val
				isCon[i - 1] = True
				i -= 1
			else:
				break
		while j < n - 1:
			if isCon[j]:
				break
			if a[j + 1] % cur_val == 0:
				ans += cur_val
				isCon[j] = True
				j += 1
			else:
				break
	for i in range(n - 1):
		if not isCon[i]:
			ans += p
	print(ans)


import sys
input = sys.stdin.readline
from operator import itemgetter
t = int(input())
for tests in range(t):
	(n, p) = map(int, input().split())
	A = list(map(int, input().split()))
	W = [p] * (n - 1)
	B = [(A[i], i) for i in range(n)]
	B.sort(key=itemgetter(0))
	for (x, i) in B:
		for j in range(i - 1, -1, -1):
			if A[j] % x == 0 and W[j] > x:
				W[j] = x
			else:
				break
		for j in range(i + 1, n):
			if A[j] % x == 0 and W[j - 1] > x:
				W[j - 1] = x
			else:
				break
	print(sum(W))


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	vals = []
	d = {}
	for i in range(n):
		vals.append((a[i], i))
		d[i] = a[i]
	vals = sorted(vals)
	ok = []
	taken = set()
	counter = -1
	while 1:
		counter += 1
		if counter == n:
			break
		p = vals[counter]
		val = p[0]
		ind = p[1]
		if ind in taken:
			continue
		taken.add(ind)
		org = ind
		a = b = org
		while 1:
			org -= 1
			if org < 0:
				a = 0
				break
			if d[org] % val != 0:
				a = org + 1
				break
			else:
				if org in taken:
					a = org
					break
				taken.add(org)
		while 1:
			ind += 1
			if ind == n:
				b = n - 1
				break
			if d[ind] % val != 0:
				b = ind - 1
				break
			else:
				if ind in taken:
					b = ind
					break
				taken.add(ind)
		ok.append((a, b, val))
	ok = sorted(ok)
	ans = min(ok[0][2], m) * (ok[0][1] - ok[0][0])
	last = ok[0][1]
	for i in ok[1:]:
		ans += (i[0] - last) * m
		ans += min(i[2], m) * (i[1] - i[0])
		last = i[1]
	print(ans)


from sys import stdin, stdout

def gcd_and_mst(n, p, a_a):
	ai_a = [[a_a[i], i] for i in range(n)]
	ai_a.sort()
	res = (n - 1) * p
	visited = set()
	for ai in ai_a:
		if ai[0] >= p:
			break
		if ai[1] in visited:
			continue
		visited.add(ai[1])
		l = r = ai[1]
		while l - 1 >= 0 and gcd(a_a[l - 1], ai[0]) == ai[0]:
			l -= 1
			res -= p - ai[0]
			if l in visited:
				break
			visited.add(l)
		while r + 1 < n and gcd(a_a[r + 1], ai[0]) == ai[0]:
			r += 1
			res -= p - ai[0]
			if r in visited:
				break
			visited.add(r)
	return res

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(stdin.readline())
for _ in range(t):
	(n, p) = map(int, stdin.readline().split())
	a_a = list(map(int, stdin.readline().split()))
	r = gcd_and_mst(n, p, a_a)
	stdout.write(str(r) + '\n')


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	locs = []
	for i in range(n):
		locs.append([a[i], i])
	locs.sort()
	weight = 0
	comps = n
	used = [0] * n
	parent = list(range(n))
	sizes = [1] * n

	def find_parent(i):
		if parent[i] == i:
			return i
		parent[i] = find_parent(parent[i])
		return parent[i]

	def union_sets(a, b):
		a = find_parent(a)
		b = find_parent(b)
		if a != b:
			if sizes[a] < sizes[b]:
				(a, b) = (b, a)
			sizes[a] += sizes[b]
			parent[b] = a
	for (mn, i) in locs:
		if mn >= p:
			break
		if used[i]:
			continue
		l = i
		r = i
		while l > 0 and a[l - 1] % mn == 0 and (not used[l - 1]):
			l -= 1
		while r < n - 1 and a[r + 1] % mn == 0 and (not used[r + 1]):
			r += 1
		if l != r:
			used[l] = 1
			for i in range(l + 1, r + 1):
				used[i] = 1
				union_sets(i - 1, i)
			comps -= r - l
			weight += mn * (r - l)
		if l > 0 and a[l - 1] % mn == 0:
			used[l] = 1
			union_sets(l - 1, l)
			weight += mn
			comps -= 1
		if r < n - 1 and a[r + 1] % mn == 0:
			used[r] = 1
			union_sets(r, r + 1)
			weight += mn
			comps -= 1
	print(weight + (comps - 1) * p)


import sys
for _ in range(int(input())):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [(a[i], i) for i in range(n)]
	b.sort()
	UF = [x for x in range(n)]
	sizes = [1] * n
	visited = [0] * n

	def find(x):
		if UF[x] != x:
			UF[x] = find(UF[x])
		return UF[x]

	def union(x, y):
		x = find(x)
		y = find(y)
		if x == y:
			return False
		if sizes[x] < sizes[y]:
			(x, y) = (y, x)
		sizes[x] += sizes[y]
		UF[y] = x
		return True
	edges = 0
	ans = 0
	for (x, i) in b:
		if x >= p:
			break
		if visited[i]:
			continue
		for j in range(i - 1, -1, -1):
			if a[j] % x == 0:
				if union(j, i):
					visited[j] = 1
					ans += x
					edges += 1
			else:
				break
		for j in range(i + 1, n):
			if a[j] % x == 0:
				if union(j, i):
					visited[j] = 1
					ans += x
					edges += 1
			else:
				break
	print(ans + (n - 1 - edges) * p)


from collections import defaultdict
for te in range(int(input())):
	(n, p) = map(int, input().split())
	arr = list(map(int, input().split()))
	cnt = defaultdict(int)
	for (i, a) in enumerate(arr):
		cnt[a, i] += 1
	vals = sorted(cnt.keys())
	ans = p * (n - 1)
	for x in vals:
		if cnt[x] > 0:
			i = x[1] - 1
			j = x[1] + 1
			while j < n and arr[j] % x[0] == 0:
				cnt[arr[j], j] -= 1
				m = cnt[arr[j], j]
				j += 1
				if m < 0:
					break
			while i >= 0 and arr[i] % x[0] == 0:
				cnt[arr[i], i] -= 1
				m = cnt[arr[i], i]
				i -= 1
				if m < 0:
					break
			eds = j - i - 2
			if x[0] < p:
				ans = ans - p * eds + x[0] * eds
	print(ans)


import sys, os, io
input = sys.stdin.readline
T = int(input())
ans = [0] * T
for t in range(T):
	(N, P) = map(int, input().split())
	A = list(map(int, input().split()))
	lis = []
	for i in range(N):
		lis.append((A[i], i))
	lis.sort()
	linked = [False] * N
	cnt = 0
	for (a, ind) in lis:
		if a >= P:
			break
		if linked[ind]:
			continue
		linked[ind] = True
		for i in range(ind - 1, -1, -1):
			if A[i] % a != 0:
				break
			ans[t] += a
			cnt += 1
			if linked[i]:
				break
			linked[i] = True
		for i in range(ind + 1, N):
			if A[i] % a != 0:
				break
			ans[t] += a
			cnt += 1
			if linked[i]:
				break
			linked[i] = True
	ans[t] += P * (N - 1 - cnt)
print(*ans, sep='\n')


import time
import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def solve():
	(N, P) = getInts()
	A = getInts()
	used = [-1] * N
	H = []
	h.heapify(H)
	ans = 0
	rem = 0
	for i in range(N):
		h.heappush(H, (A[i], i))
	while H:
		(a, i) = h.heappop(H)
		if used[i] != -1:
			continue
		used[i] = i
		if a > P:
			continue
		j = i + 1
		while j < N and used[j] == -1 and (A[j] % a == 0):
			used[j] = i
			j += 1
			ans += a
		if j < N and A[j] % a == 0:
			rem += 1
			ans += a
		j = i - 1
		while j >= 0 and used[j] == -1 and (A[j] % a == 0):
			used[j] = i
			j -= 1
			ans += a
		if j >= 0 and A[j] % a == 0:
			rem += 1
			ans += a
	for i in range(len(used) - 1):
		if used[i + 1] != used[i]:
			ans += P
	ans -= rem * P
	return ans
for _ in range(getInt()):
	print(solve())


import sys
input = sys.stdin.readline

class DisjointSetUnion:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		acopy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while acopy != a:
			(self.parent[acopy], acopy) = (a, self.parent[acopy])
		return a

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets
for _ in range(int(input())):
	(n, p) = [int(t) for t in input().split()]
	a = [int(t) for t in input().split()]
	edges = [(p, i, i + 1) for i in range(n - 1)]
	order = sorted(range(n), key=lambda i: a[i])
	uf = DisjointSetUnion(n)
	for i in order:
		for delta in (-1, +1):
			j = delta
			while 0 <= i + j < n:
				if a[i + j] % a[i] == 0 and uf.find(i + j) != uf.find(i):
					uf.union(i + j, i)
					edges.append((a[i], i + j, i))
					j += delta
				else:
					break
	uf = DisjointSetUnion(n)
	ans = 0
	edges.sort()
	for (w, u, v) in edges:
		if uf.find(u) != uf.find(v):
			uf.union(u, v)
			ans += w
	print(ans)


I = lambda : map(int, input().split())
(t,) = I()
for test in range(t):
	(n, p) = I()
	a = (*I(),)
	b = [p] * (n - 1)
	c = a[0]
	for i in range(1, n):
		if a[i] % c < 1:
			b[i - 1] = min(c, b[i - 1])
		else:
			c = a[i]
	c = a[n - 1]
	for i in range(n - 2, -1, -1):
		if a[i] % c < 1:
			b[i] = min(c, b[i])
		else:
			c = a[i]
	print(sum(b))


class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self.right = [n for n in range(N)]
		self.left = [n for n in range(N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
			self.right[gy] = max(self.right[gy], self.right[gx])
			self.left[gy] = min(self.left[gy], self.left[gx])
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]
			self.right[gx] = max(self.right[gy], self.right[gx])
			self.left[gx] = min(self.left[gy], self.left[gx])

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

	def Right(self, x):
		return self.right[self.find_root(x)]

	def Left(self, x):
		return self.left[self.find_root(x)]
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def solve(n, p, a):
	idx = [i for i in range(n)]
	idx.sort(key=lambda i: a[i])
	uf = UnionFindVerSize(n)
	Seg = SegmentTree(a, lambda x, y: gcd(x, y), 0)
	res = 0
	for i in idx:
		if a[i] > p:
			break
		while True:
			R = uf.Right(i)
			if R == n - 1:
				break
			GCD = Seg.query(i, R + 1)
			if GCD != a[i]:
				break
			if a[R + 1] % a[i] == 0:
				uf.unite(i, R + 1)
				res += a[i]
			else:
				break
		while True:
			L = uf.Left(i)
			if L == 0:
				break
			GCD = Seg.query(L, i + 1)
			if GCD != a[i]:
				break
			if a[L - 1] % a[i] == 0:
				uf.unite(i, L - 1)
				res += a[i]
			else:
				break
	res += (uf.group - 1) * p
	return res
ans = []
for _ in range(int(input())):
	(n, p) = mi()
	a = li()
	ans.append(solve(n, p, a))
print(*ans, sep='\n')


class DisjointSets:

	def __init__(self, n):
		self.p = list(range(n))
		self.rank = [0] * n

	def find_set(self, x):
		if self.p[x] != x:
			self.p[x] = self.find_set(self.p[x])
		return self.p[x]

	def link(self, x, y):
		if self.rank[x] > self.rank[y]:
			self.p[y] = x
		else:
			self.p[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def union(self, x, y):
		self.link(self.find_set(x), self.find_set(y))

def solve(n, a, p):
	order = list(range(n))
	order.sort(key=lambda i: a[i])
	ds = DisjointSets(n)
	res = 0
	for i in order:
		if a[i] >= p:
			break
		for delta in range(-1, 2, 2):
			j = i + delta
			while 0 <= j < n and a[j] % a[i] == 0 and (ds.find_set(i) != ds.find_set(j)):
				res += a[i]
				ds.union(i, j)
				j += delta
	for i in range(1, n):
		if ds.find_set(i - 1) != ds.find_set(i):
			ds.union(i - 1, i)
			res += p
	return res
t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(n, a, p))


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [p] * (n - 1)
	cur = a[0]
	for i in range(1, n):
		if a[i] % cur == 0:
			b[i - 1] = min(cur, b[i - 1])
		else:
			cur = a[i]
	cur = a[n - 1]
	for i in range(n - 2, -1, -1):
		if a[i] % cur == 0:
			b[i] = min(cur, b[i])
		else:
			cur = a[i]
	print(sum(b))


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

@bootstrap
def dfs(r, p, path):
	path[c[r]] += 1
	if path[c[r]] == 1:
		ans.append(r + 1)
	for ch in g[r]:
		if ch != p:
			yield dfs(ch, r, path)
	path[c[r]] -= 1
	yield None
t = N()
for i in range(t):
	(n, p) = RL()
	a = RLL()
	uf = UFS(n)
	res = sorted(range(n), key=lambda x: a[x])
	ans = 0
	for i in range(n):
		cur = res[i]
		if a[cur] >= p:
			break
		l = cur - 1
		while l >= 0 and uf.find(l) != uf.find(cur) and (a[l] % a[cur] == 0):
			uf.union(l, cur)
			ans += a[cur]
			l -= 1
		r = cur + 1
		while r < n and uf.find(r) != uf.find(cur) and (a[r] % a[cur] == 0):
			uf.union(r, cur)
			ans += a[cur]
			r += 1
	s = set()
	for i in range(n):
		s.add(uf.find(i))
	ans += (len(s) - 1) * p
	print(ans)