M. Little t's GCD
time limit per test
2 seconds
memory limit per test
1024 MB
input
standard input
output
standard output

Little t gives you a sequence of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$, as well as a constant $$$P$$$. You need to partition this sequence into $$$m$$$ ($$$1 \le m \le n$$$) consecutive and non-empty subsegments. Each element must belong to exactly one subsegment. Suppose one of the subsegments you obtain is $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$). For any given subsegment $$$[L, R]$$$, we define $$$W(L, R)$$$ as the sum of all positive odd numbers corresponding to the indices in this interval. Formally, $$$$$$W(L, R) = \sum_{i=L}^R (2i - 1)$$$$$$ At the same time, define $$$G(L, R)$$$ as the greatest common divisor of all elements in this interval. Formally, $$$$$$G(L, R) = \gcd(a_L, a_{L+1}, \dots, a_R)$$$$$$ Each time you create a subsegment, a cost of $$$P$$$ is incurred. Therefore, for the interval $$$[L, R]$$$, its weight is calculated as follows: $$$$$$\mathcal{E}(L, R) = W(L, R) \times G(L, R) - P$$$$$$ Little t wants you to find a partition scheme such that the total weight of these $$$m$$$ subsegments is as large as possible.

Input

The input contains multiple test cases.

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), denoting the number of test cases.

For each test case, the first line contains two integers $$$n, P$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le P \le 10^{14}$$$).

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

It is guaranteed that the sum of all $$$n$$$ over a single test file does not exceed $$$10^5$$$.

Output

For each test case, output one integer representing the answer.

Example
Input
1
3 25
8 12 6
Output
6