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:
Output Format:
For each test case, print the maximum possible score you can obtain.
Constraints:
1<=T<=10
2<=N<=105
1<=A[i],K<=109
First test case:
If we increment the whole array by K=1, the array becomes [6,5,4].
The score of this array is (5%6)+(4%5)=5+4=9.
It can be shown that this is the maximum possible score. Thus, the answer is 9.
Second test case:
If we do not increment any subarray, the score of A is 11%7=4.
It can be shown that this is the maximum possible score. Thus, the answer is 4.