You are given an array \(A\) of length \(N\). You are also given an integer, \(K\). You can increment all elements of any subarray of \(A\) by \(K\), at most once.

Let us define the score of \(A\) as the sum of \(A[ i ] \% A[ i - 1]\), for all \(i\) in the range \([1, N - 1]\). Find the maximum possible score you can obtain.

Input Format:

• The first line of input contains a single integer \(T\), which denotes the number of test cases.
• The first line of each testcase contains two integers, \(N\) and \(K\), denoting the length of the array \(A\), and the increment amount respectively.
• The second line of each testcase contains \(N\) integers, denoting the array \(A\).

Output Format:

For each test case, print the maximum possible score you can obtain.

Constraints:

\(1 <= T <= 10\)

\(2 <= N <= 10^5\)

\(1 <= A[i], K <= 10^9\)