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$