• # For Solution

circular array of length NN is defined as follows: NN integers A1,A2,,ANA1,A2,…,AN are placed in a circle in such a way that for each 1i<N1≤i<NAiAi and Ai+1Ai+1 are adjacent, and A1A1 and ANAN are also adjacent.

You are given a circular array AA of length NN. At the end of each second, the following changes are executed in the array: If Ai>0Ai>0 then the elements which are adjacent to AiAi, will get incremented by 11, for all 1iN1≤i≤N.

For example, consider the array A=[0,0,0,2,0,0,0,5]A=[0,0,0,2,0,0,0,5].

• Initially A4A4 and A8A8 are greater than zero. So after one second, A3A3A5A5A1A1 and A7A7 will get incremented by 11. Hence the array will become A=[1,0,1,2,1,0,1,5]A=[1,0,1,2,1,0,1,5].

• After two seconds, the array becomes A=[2,2,2,4,2,2,2,7]A=[2,2,2,4,2,2,2,7]. Note that the value of A4A4 has become 44, because both, A3A3 and A5A5 were greater than zero after one second.

What will be the sum of elements present in the array AA after KK seconds?

### Input Format

• The first line will contain TT, number of testcases. Then TT testcases follow.
• The first line of each testcase contains 2 space separated integers NN and KK.
• The second line of each testcase line contains NN integers A1,A2,,ANA1,A2,…,AN.

### Output Format

For each testcase, output in a single line containing the sum of the all the elements present in the array AA after KK seconds.

### Constraints

• 1T1041≤T≤104
• 3N1053≤N≤105
• 0Ai1060≤Ai≤106
• 0K1090≤K≤109
• Sum of NN over all test cases does not exceed 106106.

### Sample Input 1

4
6 1
0 1 0 1 0 0
3 0
0 1 2
8 2
0 0 0 2 0 0 0 5
3 10
1 2 3


### Sample Output 1

6
3
23
66


### Explanation

Test Case 1: After one second, the array will become A=[1,1,2,1,1,0]A=[1,1,2,1,1,0]. So the sum of elements present in the array is = 1+1+2+1+1+0=61+1+2+1+1+0=6.

Test Case 2: No change will be executed in the array as K=0K=0. So the required sum will be equal to 3.