给定一个由 $$$n$$$ ($$$n \geq 2$$$) 个正整数组成的数组 $$$a$$$ 和一个整数 $$$p$$$。考虑 $$$n$$$ 顶点的无向加权图,编号从 $$$1$$$ 到 $$$n$$$,其中顶点 $$$i$$$ 和 $$$j$$$ ($$$i<j$$$) 之间的边按以下方式添加:
- 如果 $$$gcd(a_i, a_{i+1}, a_{i+2}, \dots, a_{j}) = min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$$$,则存在权重 $$$min(a_i, a_{i+1}, a_{i+2}) 的边, \dots, a_j)$$$ 介于 $$$i$$$ 和 $$$j$$$ 之间。
- 如果 $$$i+1=j$$$,则 $$$i$$$ 和 $$$j$$$ 之间存在权重 $$$p$$$ 的边缘。
这里 $$$gcd(x, y, \ldots)$$$ 表示整数 $$$x$$$, $$$y$$$, .... 的最大公约数 (GCD)
请注意,如果上述两个条件都成立,则 $$$i$$$ 和 $$$j$$$ 之间可能存在多条边,并且如果 $$$i$$$ 和 $$$j$$$ 的两个条件均不成立,则这些顶点之间没有边。
目标是找到该图的最小生成树的权重。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) 和 $$$p$$$ ($$$1 \leq p \leq 10^9$$$) - 节点数和参数 $$$p$$$。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
输出 $$$t$$$ 行。对于每个测试用例,打印相应图表的权重。
示例
输入 #1
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
输出 #1
5 3 12 46
注意
以下是该示例的四个测试用例的图表(图表中可能的 MST 的边缘标记为粉红色):
对于测试用例 1
对于测试用例 2
对于测试用例 3
对于测试用例 4