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.

见题面 Input 部分

见题面 Output 部分

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