A circular array of length N is defined as follows: N integers A_{1},A_{2},…,A_{N} are placed in a circle in such a way that for each 1 ≤ i < N, A_{i} and A_{i+1} are adjacent, and A_{1} and A_{N} are also adjacent.

You are given a circular array A of length N. At the end of each second, the following changes are executed in the array: If A_{i} > 0 then the elements which are adjacent to A_{i}, will get incremented by 1, for all 1 ≤ i ≤ N.

For example, consider the array A = [0, 0, 0, 2, 0, 0, 0, 5]. 
Initially A_{4} and A_{8} are greater than zero. So after one second, A_{3}, A_{5}, A_{1} and A_{7} will get incremented by 1. Hence the array will become A = [1, 0, 1, 2, 1, 0, 1, 5].

After two seconds, the array becomes A = [2, 2, 2, 4, 2, 2, 2, 7]. Note that the value of A_{4} has become 4, because both, A_{3} and A_{5} were greater than zero after one second.

What will be the sum of elements present in the array A after K seconds?

------ Input Format ------ 

- The first line will contain T, number of testcases. Then T testcases follow.
- The first line of each testcase contains 2 space separated integers N and K.
- The second line of each testcase line contains N integers A_{1}, A_{2}, \dots, A_{N}. 

------ Output Format ------ 

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

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$3 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{6}$
$0 ≤ K ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- 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 1 ------ 
Test Case 1: After one second, the array will become $A = [1, 1, 2, 1, 1, 0]$. So the sum of elements present in the array is = $1 + 1 + 2 + 1 + 1 + 0 = 6$.

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

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Constructive algorithms

Ad-hoc
Skill types: Dynamic programming

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, l) = map(int, input().split())
	L = list(map(int, input().split()))
	s = sum(L)
	count_0 = L.count(0)
	if count_0 == n:
		print(0)
		continue
	for i in range(n - 1, -1, -1):
		if L[i] == 0:
			pass
		else:
			k = i
			break
	N = [0] * n
	a = n - i - 1
	for i in range(0, n):
		if L[i] == 0:
			a += 1
			N[i] = a
		else:
			a = 0
	for i in range(0, n):
		if L[i] == 0:
			pass
		else:
			k = i
			break
	a = i
	for i in range(n - 1, -1, -1):
		if L[i] == 0:
			a += 1
			N[i] = min(a, N[i])
		else:
			a = 0
	ans = s
	for i in range(n):
		a = N[i]
		b = max(0, l - a)
		ans += 2 * b
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = []
	ans = 0
	g = False
	for j in range(n):
		if a[j] > 0:
			g = True
			p.append(j)
			ans += a[j]
	if g == False:
		print(0)
		continue
	p.append(n + p[0])
	p.insert(0, p[-2] - n)
	l = 0
	m = []
	for j in range(n):
		if a[j] > 0:
			l += 1
			m.append(0)
			continue
		l2 = p[l]
		r2 = p[l + 1]
		m.append(min(j - l2, r2 - j))
	for j in range(n):
		ans += 2 * max(0, k - m[j])
	print(ans)


cases = int(input())
for i in range(cases):
	(N, K) = map(int, input().split(' '))
	li = list(map(int, input().split(' ')))
	pos = []
	ans = 0
	gthanzero = False
	for k in range(N):
		if li[k] > 0:
			gthanzero = True
			pos.append(k)
			ans += li[k]
	if gthanzero == False:
		print(0)
		continue
	pos.append(N + pos[0])
	pos.insert(0, pos[-2] - N)
	l = 0
	min_time = []
	for k in range(N):
		if li[k] > 0:
			l += 1
			min_time.append(0)
			continue
		L = pos[l]
		R = pos[l + 1]
		min_time.append(min(k - L, R - k))
	for k in range(N):
		ans += 2 * max(0, K - min_time[k])
	print(ans)


import sys
MOD = 1000000007

def inp():
	return sys.stdin.readline().strip()

def ii():
	return int(inp())

def iis():
	return [int(i) for i in inp().split()]

def solve():
	(n, k) = iis()
	a = iis()
	distToNonZero = [MOD for _ in range(n)]
	val = MOD
	for i in range(2 * n):
		distToNonZero[i % n] = min(distToNonZero[i % n], abs(val - i))
		if a[i % n] != 0:
			distToNonZero[i % n] = 0
			val = i
	val = MOD
	for i in range(2 * n, -1, -1):
		distToNonZero[i % n] = min(distToNonZero[i % n], abs(val - i))
		if a[i % n] != 0:
			distToNonZero[i % n] = 0
			val = i
	s = sum(a)
	for dist in distToNonZero:
		s += max(0, k - dist) * 2
	return s
t = ii()
for _ in range(t):
	print(solve())


import math
import os
import random
import re
import sys
t = int(input())
while t:
	t -= 1
	(N, K) = map(int, input().split())
	lis = list(map(int, input().rstrip().split()))
	vvv = [0] * N
	if lis == vvv:
		print(0)
		continue
	liss = []
	res = sum(lis) + 2 * K * N
	for i in range(N):
		if lis[i] != 0:
			liss.append(i)
	if liss == []:
		print(res)
		continue
	nn = len(liss)
	list2 = []
	for i in range(nn - 1):
		jjj = liss[i + 1] - liss[i] - 1
		if jjj:
			list2.append(jjj)
	list2.append(N - 1 - liss[-1] + liss[0])
	for m in list2:
		if m % 2:
			c = m // 2 + 1
			if c <= K:
				res -= 2 * (c * c)
			else:
				res -= 2 * (2 * c * K - K * K)
		else:
			c = m // 2
			if c <= K:
				res -= 2 * (c * (c + 1))
			else:
				res -= 2 * (2 * c * K - K * K + K)
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if list(set(a)) == [0]:
		print(0)
		continue
	time = [0] * n
	non_zero = [0] + [i for i in range(n) if a[i] > 0]
	non_zero[0] = non_zero[-1] - n
	non_zero.append(non_zero[1] + n)
	l = 0
	L = 0
	R = 0
	for i in range(n):
		if a[i] > 0:
			continue
		while non_zero[l + 1] < i:
			l += 1
		L = non_zero[l]
		R = non_zero[l + 1]
		time[i] = min(R - i, i - L)
	ans = sum(a)
	for i in range(n):
		ans += 2 * max(0, k - time[i])
	print(ans)


def solveA():
	direction = ['North', 'East', 'South', 'West']
	for _ in range(int(input())):
		print(direction[int(input()) % 4])

def solveB():
	for _ in range(int(input())):
		(N, S) = [int(x) for x in input().split()]
		print(S if S <= N else 2 * N - S)

def solveC():
	for _ in range(int(input())):
		(N, S) = [int(x) for x in input().split()]
		ans = N * (N + 1) // 2 - S
		print(ans if ans >= 1 and ans <= N else -1)

def solveD():
	for _ in range(int(input())):
		N = int(input())
		if N == 2:
			print(*[-1, -1], '\n', *[-1, -1])
			continue
		for i in range(N):
			print(*[-1 if x == i else 1 for x in range(N)])

def solveE():

	def findBoth(lst):
		new = set()
		for i in lst:
			if i == 0:
				if N - 1 not in zero and 1 not in zero:
					new.add(0)
			elif i == N - 1:
				if N - 2 not in zero and 0 not in zero:
					new.add(N - 1)
			elif i - 1 not in zero and i + 1 not in zero:
				new.add(i)
		non_zero.difference_update(new)
		return len(new)
	for _ in range(int(input())):
		(N, K) = [int(x) for x in input().split()]
		A = [int(x) for x in input().split()]
		(zero, non_zero, LR) = (set(), set(), set())
		for i in range(N):
			if A[i]:
				non_zero.add(i)
			else:
				zero.add(i)
		ans = sum(A)
		if not ans:
			print(0)
			continue
		both = findBoth(non_zero)
		while zero and K:
			ans += 2 * len(non_zero)
			ans += 2 * both
			K -= 1
			temp = set()
			for i in non_zero:
				if i + 1 < N:
					if i + 1 in zero:
						temp.add(i + 1)
				elif 0 in zero:
					temp.add(0)
				if i - 1 >= 0:
					if i - 1 in zero:
						temp.add(i - 1)
				elif N - 1 in zero:
					temp.add(N - 1)
			zero.difference_update(temp)
			non_zero.update(temp)
			both += findBoth(non_zero)
		print(ans + 2 * both * K)
solveE()


import sys
from collections import Counter

def soln(xs, k):
	distances = xs[:]
	try:
		start = next((i for (i, x) in enumerate(xs) if x > 0))
	except StopIteration:
		return 0
	closest = start
	for i in range(closest, closest + len(xs)):
		i = i % len(xs)
		if xs[i] > 0:
			distances[i] = 0
			closest = i
			continue
		distances[i] = (i - closest) % len(xs)
	closest = start
	for i in range(closest, closest - len(xs), -1):
		i = i % len(xs)
		if xs[i] > 0:
			closest = i
			continue
		distances[i] = min(distances[i], (closest - i) % len(xs))
	born_at = Counter(distances)
	all_born_at = max(born_at.keys())
	(total, active, secs_left) = (0, 0, k)
	for i in range(all_born_at):
		if secs_left == 0:
			break
		secs_left -= 1
		active += born_at[i]
		total += 2 * active
	return sum(xs) + total + 2 * len(xs) * secs_left
data = sys.stdin.readlines()
data = data[1:]
for i in range(len(data) // 2):
	(n, k) = [int(x) for x in data[2 * i].split()]
	arr = [int(x) for x in data[2 * i + 1].split()]
	print(soln(arr, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * n
	c = [0] * n
	if a.count(0) == n:
		print(0)
		continue
	else:
		for i in range(n):
			if a[i] != 0:
				l = i
				break
		for i in range(n - 1, -1, -1):
			if a[i] != 0:
				r = i
				break
		cur = 0
		for i in range(l, n):
			if a[i] != 0:
				cur = 0
			else:
				cur += 1
				b[i] = cur
		for i in range(l):
			if a[i] != 0:
				cur = 0
			else:
				cur += 1
				b[i] = cur
		cur = 0
		for i in range(r, -1, -1):
			if a[i] != 0:
				cur = 0
			else:
				cur += 1
				c[i] = cur
		for i in range(n - 1, r, -1):
			if a[i] != 0:
				cur = 0
			else:
				cur += 1
				c[i] = cur
		for i in range(n):
			b[i] = min(c[i], b[i])
		s = 0
		for i in range(n):
			if a[i] != 0:
				s += a[i] + 2 * k
			elif b[i] != 0 and b[i] < k:
				s += 2 * (k - b[i])
		print(s)


from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	q = deque()
	vis = [False] * n
	for i in range(n):
		if l[i] != 0:
			vis[i] = True
			q.append([i, 0])
	day = [0] * n
	it = 0
	while q:
		x = q.popleft()
		it += 1
		day[x[1]] += 1
		i = x[0]
		if vis[(i + 1) % n] == False:
			vis[(i + 1) % n] = True
			q.append([(i + 1) % n, x[1] + 1])
		if i - 1 < 0 and vis[n - 1] == False:
			vis[n - 1] = True
			q.append([n - 1, x[1] + 1])
		if i - 1 >= 0 and vis[i - 1] == False:
			vis[i - 1] = True
			q.append([i - 1, x[1] + 1])
	t = 0
	if s == 0:
		print(0)
	else:
		for i in range(n):
			if k == 0:
				break
			t += day[i]
			s += t * 2
			k -= 1
		if k == 0:
			print(s)
		else:
			print(k * n * 2 + s)


from collections import deque, defaultdict, Counter
from itertools import product, groupby, permutations, combinations, accumulate, zip_longest, combinations_with_replacement
from math import gcd, floor, inf, log2, sqrt, log10, factorial
from bisect import bisect_right, bisect_left, insort_left
from statistics import mode
from string import ascii_lowercase, ascii_uppercase
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, nlargest, nsmallest, merge
from copy import deepcopy
cases = int(input())
for _ in range(cases):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sm = sum(arr)
	kk = k
	if sm == 0:
		print(0)
	else:
		ans = sm
		for (ind, n) in enumerate(arr):
			if n != 0:
				arr = arr[ind:] + arr[:ind]
				break
		arr = [1 if i != 0 else 0 for i in arr]
		for (number, grp) in groupby(arr):
			ln = len(list(grp))
			if number != 0:
				ans += ln * k * 2
			else:
				for i in range(ln):
					ans += 2 * max(0, k - min(i + 1, ln - i))
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	large = 0
	xx = sum(lis)
	if xx == 0:
		print(0)
		continue
	for i in range(n):
		if lis[i] > 0:
			large = i
			break
	left = [0] * n
	l = large
	new_l = 0
	for i in range(n):
		if lis[large % n] > 0:
			left[large % n] = 0
			new_l = 1
		else:
			left[large % n] = new_l
			new_l += 1
		large += 1
	for i in range(n):
		if lis[l % n] > 0:
			left[l % n] = 0
			new_l = 1
		else:
			left[l % n] = min(left[l % n], new_l)
			new_l += 1
		l -= 1
	print((k * n - sum([min(left[i], k) for i in range(n)])) * 2 + xx)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	x = n - l.count(0)
	s = sum(l)
	ans = s + k * n * 2
	if s == 0:
		print(0)
		continue
	d = []
	for i in range(n):
		if l[i] != 0:
			d.append(i)
	d.append(d[0] + n)
	for i in range(len(d) - 1):
		x1 = d[i]
		x2 = d[i + 1]
		z = abs(x1 - x2) - 1
		if z == 0:
			continue
		i1 = 1
		i2 = z
		f = k
		while i1 <= i2 and f > 0:
			ans -= 2 * (i2 - i1 + 1)
			i1 += 1
			i2 -= 1
			f -= 1
			if f == 0:
				break
	print(ans)


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	closest = [None] * N
	ans = 0
	ind = None
	for i in range(N):
		ans += arr[i]
		if not arr[i]:
			if ind != None:
				closest[i] = i - ind
		else:
			ind = i
			closest[i] = 0
	if ind == None:
		print(0)
		continue
	for i in range(N):
		if closest[i] == None:
			closest[i] = (i - ind) % N
		else:
			break
	ind = None
	for i in range(N - 1, -1, -1):
		if not arr[i]:
			if ind != None:
				ans += max(K - min(closest[i], ind - i), 0) * 2
		else:
			ind = i
			ans += K * 2
	for i in range(N - 1, -1, -1):
		if not arr[i]:
			ans += max(K - min(closest[i], (ind - i) % N), 0) * 2
		else:
			break
	print(ans)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	left = -1
	for i in range(N):
		if A[i] > 0:
			left = i
			break
	right = -1
	for i in range(N - 1, -1, -1):
		if A[i] > 0:
			right = i
			break
	time = [0] * N
	if left != -1:
		i = (left + 1) % N
		dis = 1
		while i != left:
			if A[i] > 0:
				dis = 0
			else:
				time[i] = dis
			dis += 1
			i = (i + 1) % N
	if right != -1:
		i = (right - 1 + N) % N
		dis = 1
		while i != right:
			if A[i] > 0:
				dis = 0
			else:
				time[i] = min(dis, time[i])
			dis += 1
			i = (i - 1 + N) % N
	ans = 0
	for i in range(N):
		ans += A[i]
		ans += max(0, K - time[i]) * 2
	if left == -1:
		print(sum(A))
	else:
		print(ans)


from bisect import bisect_right

def intArr():
	return map(int, input().split())

def In():
	return int(input())

def func():
	(n, k) = intArr()
	arr = list(intArr())
	if sum((i > 0 for i in arr)) == 0:
		return 0
	l1 = [i for i in range(n) if arr[i]]
	m = len(l1)
	for i in range(n):
		if arr[i] == 0:
			idx = bisect_right(l1, i)
			if idx == 0:
				arr[i] = -2 * min(l1[0] - i, n - l1[-1] + i)
			elif idx == m:
				arr[i] = -2 * min(i - l1[-1], n - i + l1[0])
			else:
				arr[i] = -2 * min(l1[idx] - i, i - l1[idx - 1])
		arr[i] += 2 * k
	return sum((i for i in arr if i > 0))

def main():
	for _ in range(In()):
		print(func())
	return
main()


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	time = [0] * N
	left = -1
	for j in range(N):
		if arr[j] > 0:
			left = j
			break
	right = -1
	for j in range(N - 1, -1, -1):
		if arr[j] > 0:
			right = j
			break
	if left == -1:
		print(0)
		continue
	curr = 1
	j = (left + 1) % N
	while j != left:
		if arr[j] > 0:
			curr = 0
		else:
			time[j] = curr
		curr += 1
		j = (j + 1) % N
	curr = 1
	j = (right - 1 + N) % N
	while j != right:
		if arr[j] > 0:
			curr = 0
		else:
			time[j] = min(time[j], curr)
		curr += 1
		j = (j - 1 + N) % N
	s = 0
	for j in range(N):
		s += arr[j]
		s += max(0, K - time[j]) * 2
	print(s)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	net = sum(a)
	if net == 0:
		print(0)
		t -= 1
		continue
	pre = [0] * n
	suf = [0] * n
	count = 0
	for i in range(n):
		if a[i] > 0:
			count = 0
		else:
			count += 1
		pre[i] = count
	i = 0
	while a[i] == 0:
		pre[i] += pre[n - 1]
		i += 1
	count = 0
	for j in range(n - 1, -1, -1):
		if a[j] > 0:
			count = 0
		else:
			count += 1
		suf[j] = count
	j = n - 1
	while a[j] == 0:
		suf[j] += suf[0]
		j -= 1
	for i in range(n):
		count = min(pre[i], suf[i])
		if count < k:
			net += 2 * (k - count)
	print(net)
	t -= 1


for _ in range(int(input())):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	zeros = []
	count = 0
	for i in b:
		if i == 0:
			count += 1
		elif count > 0:
			zeros.append(count)
			count = 0
	if count > 0:
		if len(zeros) == 0 or b[0] != 0:
			zeros.append(count)
		else:
			zeros[0] += count
	ans = sum(b)
	if ans == 0:
		print(0)
		continue
	while zeros.count(0) != len(zeros) and a[1] > 0:
		ans = ans + (a[0] - sum(zeros)) * 2
		for i in range(len(zeros)):
			if zeros[i] > 1:
				zeros[i] -= 2
			elif zeros[i] == 1:
				zeros[i] -= 1
		a[1] -= 1
	ans = ans + a[0] * 2 * a[1]
	print(ans)


for t in range(int(input())):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	time = [0] * N
	(l, r) = (None, None)
	for (ind, val) in enumerate(arr):
		if val > 0:
			l = ind
			break
	for i in range(N - 1, -1, -1):
		if arr[i] > 0:
			r = i
			break
	if l is None:
		print(0)
	else:
		curr1 = (l + 1) % N
		it = 1
		while curr1 != l:
			if arr[curr1] > 0:
				time[curr1] = 0
				it = 1
			else:
				time[curr1] = it
				it += 1
			curr1 = (curr1 + 1) % N
		curr2 = r - 1
		it = 1
		while curr2 != r:
			if curr2 == -1:
				curr2 = N - 1
				continue
			if arr[curr2] > 0:
				time[curr2] = 0
				it = 1
			else:
				time[curr2] = min(time[curr2], it)
				it += 1
			curr2 -= 1
		ans = sum(arr)
		for i in time:
			ans += max(0, (K - i) * 2)
		print(ans)


from collections import deque
import sys
for tc in range(int(input())):
	ls = list(map(int, input().split()))
	lk = list(map(int, input().split()))
	que = deque()
	su = 0
	vis = [0] * len(lk)
	dis = [sys.maxsize] * len(lk)
	for x in range(len(lk)):
		if lk[x] > 0:
			que.append(x)
			vis[x] = 1
			dis[x] = 0
	while len(que) > 0:
		front = que.popleft()
		l = (front - 1 + len(lk)) % len(lk)
		r = (front + 1) % len(lk)
		if vis[l] == 0:
			dis[l] = dis[front] + 1
			que.append(l)
			vis[l] = 1
		if vis[r] == 0:
			dis[r] = dis[front] + 1
			que.append(r)
			vis[r] = 1
	for x in range(len(dis)):
		su += lk[x]
		if ls[1] - dis[x] > 0:
			su += (ls[1] - dis[x]) * 2
	print(su)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ln = []
	if k == 0:
		print(sum(l))
		continue
	if sum(l) == 0:
		print(0)
		continue
	for i in range(-1, -n, -1):
		if l[i] > 0:
			xi = i
			break
	d = xi * -1 - 1
	for i in range(n):
		if l[i] > 0:
			ln.append(0)
			d = 0
		else:
			d += 1
			ln.append(d)
	for i in range(n):
		if l[i] > 0:
			xi = i
			break
	d = xi
	f = 0
	for i in range(-1, -n - 1, -1):
		if l[i] > 0:
			d = 0
		else:
			d += 1
			ln[i] = min(ln[i], d)
	for i in range(1, n - 1):
		l[i] += max(0, k - ln[i - 1]) + max(0, k - ln[i + 1])
	l[0] += max(0, k - ln[n - 1]) + max(0, k - ln[1])
	l[n - 1] += max(0, k - ln[n - 2]) + max(0, k - ln[0])
	print(sum(l))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	l3 = []
	if k == 0:
		print(sum(l))
		continue
	if sum(l) == 0:
		print(0)
		continue
	for i in range(-1, -n, -1):
		if l[i] > 0:
			xi = i
			break
	d = xi * -1 - 1
	for i in range(n):
		if l[i] > 0:
			l1.append(0)
			l3.append(0)
			d = 0
		else:
			d += 1
			l1.append(d)
			l3.append(d)
	for i in range(n):
		if l[i] > 0:
			xi = i
			break
	d = xi
	f = 0
	for i in range(-1, -n - 1, -1):
		if l[i] > 0:
			l2.append(0)
			d = 0
		else:
			d += 1
			l2.append(d)
			l3[i] = min(l3[i], d)
	for i in range(1, n - 1):
		if k - l3[i - 1] > 0 and k - l3[i + 1] > 0:
			l[i] += 2 * k - l3[i - 1] - l3[i + 1]
		elif k - l3[i - 1] > 0:
			l[i] += k - l3[i - 1]
		elif k - l3[i + 1] > 0:
			l[i] += k - l3[i + 1]
	if k - l3[n - 1] > 0 and k - l3[1] > 0:
		l[0] += 2 * k - l3[1] - l3[n - 1]
	elif k - l3[1] > 0:
		l[0] += k - l3[1]
	elif k - l3[n - 1] > 0:
		l[0] += k - l3[n - 1]
	if k - l3[n - 2] > 0 and k - l3[0] > 0:
		l[n - 1] += 2 * k - l3[0] - l3[n - 2]
	elif k - l3[0] > 0:
		l[n - 1] += k - l3[0]
	elif k - l3[n - 2] > 0:
		l[n - 1] += k - l3[n - 2]
	sm = 0
	for i in l:
		if i > 0:
			sm += i
	print(sum(l))


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	ans = 0
	s = set()
	p = []
	for i in range(n):
		if a[i] > 0:
			ans += a[i]
			s.add(i)
			p.append(i)
	if not s:
		print(ans)
	else:
		m = len(s)
		while m < n and k:
			ans += 2 * m
			k -= 1
			x = []
			for j in p:
				l = j - 1
				r = j + 1
				if l < 0:
					l = n - 1
				if r >= n:
					r = 0
				if l not in s:
					s.add(l)
					x.append(l)
					m += 1
				if r not in s:
					s.add(r)
					x.append(r)
					m += 1
			p = x
		if k:
			ans += 2 * m * k
		print(ans)
	t -= 1


t = int(input())
while t:
	t -= 1
	(N, K) = map(int, input().split())
	lis = list(map(int, input().rstrip().split()))
	vvv = [0] * N
	if lis == vvv:
		print(0)
		continue
	liss = []
	res = sum(lis) + 2 * K * N
	for i in range(N):
		if lis[i] != 0:
			liss.append(i)
	if liss == []:
		print(res)
		continue
	nn = len(liss)
	list2 = []
	for i in range(nn - 1):
		jjj = liss[i + 1] - liss[i] - 1
		if jjj:
			list2.append(jjj)
	list2.append(N - 1 - liss[-1] + liss[0])
	for m in list2:
		if m % 2:
			c = m // 2 + 1
			if c <= K:
				res -= 2 * (c * c)
			else:
				res -= 2 * (2 * c * K - K * K)
		else:
			c = m // 2
			if c <= K:
				res -= 2 * (c * (c + 1))
			else:
				res -= 2 * (2 * c * K - K * K + K)
	print(res)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	n_arr = arr.copy()
	if any(arr) > 0:
		q = 0
		for i in range(b):
			q += 1
			for j in range(len(arr)):
				if arr[j] > 0:
					if j + 1 < a:
						n_arr[j + 1] += 1
					else:
						n_arr[0] += 1
					if j - 1 >= 0:
						n_arr[j - 1] += 1
					else:
						n_arr[a - 1] += 1
			arr = n_arr.copy()
			if all(n_arr) > 0:
				break
		ans = sum(n_arr) + a * (b - q) * 2
		print(ans)
	else:
		print(0)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	cs = 0
	zero_check = sum([x == 0 for x in a])
	if n - zero_check == 0:
		print(0)
		continue
	while cs < k:
		flag_a = [x > 0 for x in a]
		flag = n - sum(flag_a)
		if flag == 0:
			break
		for i in range(n):
			if flag_a[i]:
				a[i - 1] += 1
				a[(i + 1) % n] += 1
		cs += 1
	sum_a = sum(a)
	if cs < k:
		sum_a += 2 * n * (k - cs)
	print(sum_a)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	array = list(map(int, input().split()))
	prevSum = sum(array)
	curSum = sum(array)
	positionSet = set()
	setLen = 0
	if curSum == 0 or k == 0:
		print(curSum)
		continue
	leftMin = []
	cur = None
	for (idx, val) in enumerate(array):
		leftMin.append(cur)
		if val != 0:
			cur = idx
	idx = 0
	while idx < n and leftMin[idx] == None:
		leftMin[idx] = cur
		idx += 1
	rightMin = []
	cur = None
	for (idx, val) in enumerate(array[::-1]):
		rightMin.append(cur)
		if val != 0:
			cur = idx
	idx = 0
	while idx < n and rightMin[idx] == None:
		rightMin[idx] = cur
		idx += 1
	rightMin = [n - i - 1 for i in rightMin][::-1]
	ans = 0
	for i in range(n):
		left = leftMin[i]
		right = rightMin[i]
		if array[i]:
			if (left + 1 == i or (i == 0 and left == n - 1)) and (right - 1 == i or (i == n - 1 and right == 0)):
				ans += k * 2 + array[i]
			elif (left + 1 == i or (i == 0 and left == n - 1)) or (right - 1 == i or (i == n - 1 and right == 0)):
				ans += 1 + (k - 1) * 2 + array[i]
			else:
				ans += (k - 1) * 2 + array[i]
		else:
			leftCount = i - left if left < i else n - (left - i)
			rightCount = right - i if right > i else n - (i - right)
			if (left + 1 == i or (i == 0 and left == n - 1)) and (right - 1 == i or (i == n - 1 and right == 0)):
				ans += k * 2
			else:
				tempK = k
				if leftCount == rightCount:
					if leftCount <= tempK:
						ans += 2
						tempK -= leftCount
						if tempK:
							ans += tempK * 2
				elif abs(leftCount - rightCount) == 1:
					temp = min(rightCount, leftCount)
					if temp <= tempK:
						ans += 1
						tempK -= temp
						if tempK:
							ans += tempK * 2
				else:
					temp = min(rightCount, leftCount)
					if temp <= tempK:
						ans += 1
						tempK -= temp
						if tempK:
							ans += 1 + (tempK - 1) * 2
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if a.count(0) == n:
		print(0)
		continue
	if k == 0:
		print(sum(a))
		continue
	for i in range(k):
		ans = a.copy()
		for j in range(n):
			if a[j] > 0:
				if j == 0:
					ans[1] += 1
					ans[-1] += 1
				elif j == n - 1:
					ans[0] += 1
					ans[-2] += 1
				else:
					ans[j - 1] += 1
					ans[j + 1] += 1
		a = ans.copy()
		if a.count(0) == 0:
			break
	final_sum = 2 * n * (k - 1 - i)
	print(sum(a) + final_sum)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	listt = arr[:]
	flag = 0
	for i in listt:
		if i > 0:
			flag = 1
			break
	if flag == 0:
		print(0)
		continue
	if k == 0:
		print(sum(arr))
		continue
	a = 0
	while 0 in arr:
		for i in range(n):
			if listt[i] != 0:
				if i == n - 1:
					arr[0] += 1
					arr[i - 1] += 1
				else:
					arr[i - 1] += 1
					arr[i + 1] += 1
		a += 1
		listt = arr[:]
		if k == a:
			break
	if k > a:
		print((k - a) * n * 2 + sum(listt))
	else:
		print(sum(listt))


def func():
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set()
	for i in range(n):
		if l[i] > 0:
			s.add(i)
	while k > 0:
		if not len(s):
			k = 0
			break
		elif len(s) == n:
			break
		else:
			sample = s.copy()
			for i in sample:
				l[(i + 1) % n] += 1
				l[(i - 1) % n] += 1
				s.add((i - 1) % n)
				s.add((i + 1) % n)
		k -= 1
	return sum(l) + k * n * 2
t = int(input())
for i in range(t):
	print(func())


try:
	for _ in range(int(input())):
		(n, s) = map(int, input().split())
		l = list(map(int, input().split()))
		e = l.copy()
		if any(l) > 0:
			q = 0
			for i in range(s):
				q += 1
				for j in range(len(l)):
					if l[j] > 0:
						if j + 1 < n:
							e[j + 1] += 1
						else:
							e[0] += 1
						if j - 1 >= 0:
							e[j - 1] += 1
						else:
							e[n - 1] += 1
				l = e.copy()
				if all(e) > 0:
					break
			ans = sum(e) + n * (s - q) * 2
			print(ans)
		else:
			print(0)
except:
	pass


import sys
input = sys.stdin.readline
from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	vis = [False] * n
	stack = deque()
	for i in range(n):
		if a[i] > 0:
			stack.append((i, k))
			vis[i] = True
	while stack:
		(pos, val) = stack.popleft()
		index1 = (pos - 1) % n
		index2 = (pos + 1) % n
		a[index1] += val
		a[index2] += val
		if val > 0:
			if vis[index1] == False:
				stack.append((index1, val - 1))
			if vis[index2] == False:
				stack.append((index2, val - 1))
		vis[index1] = True
		vis[index2] = True
	print(sum(a))


def solve():
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	total = sum(arr)
	if total == 0:
		return 0
	q = [i for i in range(len(arr)) if arr[i] != 0]
	depth = 1
	non_zero_dist = [0 for _ in range(len(arr))]
	visited = set(q)
	while q:
		new_q = []
		for i in q:
			if arr[(i - 1) % n] == 0:
				if not (i - 1) % n in visited:
					new_q.append((i - 1) % n)
					non_zero_dist[(i - 1) % n] = depth
					visited.add((i - 1) % n)
			if arr[(i + 1) % n] == 0:
				if not (i + 1) % n in visited:
					new_q.append((i + 1) % n)
					visited.add((i + 1) % n)
					non_zero_dist[(i + 1) % n] = depth
		depth += 1
		q = new_q
	ans = 0
	for i in range(len(arr)):
		if arr[i] != 0:
			ans += arr[i] + k * 2
		else:
			ans += max(0, (k - non_zero_dist[i]) * 2)
	return ans
for _ in range(int(input())):
	print(solve())


test = int(input())
while test:
	(n, k) = map(int, input().split())
	o = [int(x) for x in input().split()]
	s = 0
	c = o.count(0)
	if c != n:
		while c:
			if k == 0:
				break
			a = o.copy()
			for l in range(n):
				if l != 0 and l != n - 1:
					if a[l - 1] > 0 and a[l + 1] == 0 or (a[l - 1] == 0 and a[l + 1] > 0):
						o[l] += 1
					elif a[l - 1] > 0 and a[l + 1] > 0:
						o[l] += 2
				elif l == 0:
					if a[n - 1] > 0 and a[l + 1] == 0 or (a[n - 1] == 0 and a[l + 1] > 0):
						o[l] += 1
					elif a[n - 1] > 0 and a[l + 1] > 0:
						o[l] += 2
				elif a[l - 1] > 0 and a[0] == 0 or (a[l - 1] == 0 and a[0] > 0):
					o[l] += 1
				elif a[l - 1] > 0 and a[0] > 0:
					o[l] += 2
			k -= 1
			c = o.count(0)
		s = sum(o) + 2 * k * n
	print(s)
	test -= 1


from collections import OrderedDict
t = int(input())
for i in range(0, t):
	(n, sec) = [int(x) for x in input().split()]
	vals = [int(x) for x in input().split()]
	valsum = sum(vals)
	if valsum == 0:
		print(0)
	elif sec == 0:
		print(valsum)
	elif 0 in vals:
		newvals = [x for x in vals]
		while 0 in vals:
			zc = vals.count(0)
			nzc = n - zc
			for k in range(0, n):
				if vals[k] != 0:
					newvals[k - 1] += 1
					if k == n - 1:
						newvals[0] += 1
					else:
						newvals[k + 1] += 1
			vals = [x for x in newvals]
			valsum += 2 * nzc
			sec -= 1
			if sec == 0:
				break
		print(valsum + 2 * n * sec)
	else:
		print(valsum + 2 * n * sec)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	left = [-1] * n
	right = [-1] * n
	if arr[0] > 0:
		left[0] = 0
	else:
		for i in range(n - 1, 0, -1):
			if arr[i] > 0:
				left[0] = i
				break
	for i in range(1, n):
		if arr[i] > 0:
			left[i] = i
		else:
			left[i] = left[i - 1]
	if arr[n - 1] > 0:
		right[n - 1] = n - 1
	else:
		for i in range(0, n - 1):
			if arr[i] > 0:
				right[n - 1] = i
				break
	for i in range(n - 2, -1, -1):
		if arr[i] > 0:
			right[i] = i
		else:
			right[i] = right[i + 1]
	s = sum(arr)
	if s == 0:
		print(0)
		continue
	for i in range(n):
		if arr[i] > 0:
			s += 2 * k
		else:
			l = -1
			if left[i] > i:
				l = i + n - left[i]
			else:
				l = i - left[i]
			r = -1
			if right[i] < i:
				r = n - i + right[i]
			else:
				r = right[i] - i
			ans = min(l, r)
			if k - ans > 0:
				s += 2 * (k - ans)
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if arr.count(0) == n:
		print(0)
	else:
		tempLeft = [0 for i in range(n)]
		tempRight = [0 for i in range(n)]
		i = 0
		while arr[i] == 0:
			i += 1
		left = i
		j = (i + 1) % n
		while j != i:
			if arr[j] > 0:
				left = j
			elif j > left:
				tempLeft[j] = j - left
			else:
				tempLeft[j] = n + (j - left)
			j += 1
			j %= n
		i = n - 1
		while arr[i] == 0:
			i -= 1
		right = i
		j = (i - 1) % n
		while j != i:
			if arr[j] > 0:
				right = j
			elif j < right:
				tempRight[j] = right - j
			else:
				tempRight[j] = n + (right - j)
			j -= 1
			j %= n
		temp = [min(tempRight[i], tempLeft[i]) for i in range(n)]
		x = max(temp)
		s = sum(arr)
		dic = {}
		for i in temp:
			dic[i] = dic.get(i, 0) + 1
		r = 0
		i = 0
		while i < x and i < k:
			r += dic.get(i, 0)
			s += 2 * r
			i += 1
		if x == 0:
			r = dic.get(0, 0)
		s += max(k - i, 0) * 2 * n
		print(s)


def solve(n, k, A):
	tot = 0
	cnt = 0
	lis = [1] * n
	for i in range(n):
		if A[i] == 0:
			cnt += 1
			lis[i] = 0
		tot += A[i]
	if tot == 0:
		return 0
	while cnt > 0 and k > 0:
		i = 0
		flag = False
		while i < n:
			if A[i] > 0:
				if i == n - 1 and flag:
					break
				pre = (n + i - 1) % n
				nxt = (i + 1) % n
				if A[pre] == 0:
					cnt -= 1
					if pre == n - 1:
						flag = True
				if A[nxt] == 0:
					cnt -= 1
					i += 1
				A[pre] += 1
				A[nxt] += 1
				tot += 2
			i += 1
		k -= 1
	if k == 0:
		return tot
	tot = tot + 2 * n * k
	return tot
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = [int(x) for x in input().split()]
	ans = solve(n, k, A)
	print(ans)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	f = l.copy()
	if any(l) > 0:
		r = 0
		for i in range(b):
			r += 1
			for j in range(len(l)):
				if l[j] > 0:
					if j + 1 < a:
						f[j + 1] += 1
					else:
						f[0] += 1
					if j - 1 >= 0:
						f[j - 1] += 1
					else:
						f[a - 1] += 1
			l = f.copy()
			if all(f) > 0:
				break
		ans = sum(f) + a * (b - r) * 2
		print(ans)
	else:
		print(0)


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	li = [int(x) for x in input().split()]
	su = sum(li)
	if k == 0:
		print(su)
	else:
		for i in range(k):
			c = 0
			l = [x for x in li]
			for j in range(n):
				if li[(j - 1) % n] != 0:
					c += 1
					l[j] += 1
				if li[(j + 1) % n] != 0:
					c += 1
					l[j] += 1
			li = [x for x in l]
			su = su + c
			if c == 2 * n or c == 0:
				break
		print(su + (k - i - 1) * c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	perm = set()
	if arr.count(0) == n:
		print(0)
		continue
	for i in range(n):
		if arr[i] == 0:
			perm.add(i)
	while k > 0 and len(perm) > 0:
		tem = set()
		for i in range(n):
			if i == 0:
				if i not in perm and i not in tem:
					if i + 1 in perm:
						tem.add(i + 1)
						perm.remove(i + 1)
					if n - 1 in perm:
						tem.add(n - 1)
						perm.remove(n - 1)
					arr[n - 1] += 1
					arr[i + 1] += 1
			elif i == n - 1:
				if i not in perm and i not in tem:
					if 0 in perm:
						tem.add(0)
						perm.remove(0)
					if i - 1 in perm:
						tem.add(i - 1)
						perm.remove(i - 1)
					arr[i - 1] += 1
					arr[0] += 1
			elif i not in perm and i not in tem:
				if i + 1 in perm:
					tem.add(i + 1)
					perm.remove(i + 1)
				if i - 1 in perm:
					tem.add(i - 1)
					perm.remove(i - 1)
				arr[i - 1] += 1
				arr[i + 1] += 1
		k -= 1
	if k == 0:
		print(sum(arr))
	else:
		print(sum(arr) + 2 * k * n)


def find(x):
	i = 1
	while day[x - i] > i:
		day[x - i] = i
		i = i + 1
	i = 1
	temp = (x + 1) % n
	while day[temp] > i:
		day[temp] = i
		i = i + 1
		temp = (temp + 1) % n
for _ in range(int(input())):
	ans = 0
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	pos = []
	day = [pow(10, 10)] * n
	for i in range(n):
		if l[i] > 0:
			pos.append(i)
			day[i] = 0
	for i in pos:
		find(i)
	for i in range(n):
		if day[i] <= k:
			if day[i - 1] < day[i] and day[(i + 1) % n] < day[i]:
				ans = ans + (k - day[i] + 1) * 2
			elif day[i - 1] < day[i] or day[(i + 1) % n] < day[i]:
				if day[i - 1] == day[i] or day[(i + 1) % n] == day[i]:
					if k - day[i] < 1:
						ans = ans + (k - day[i]) + 1
					else:
						ans = ans + 1 + (k - day[i]) * 2
				elif k - day[i] < 2:
					ans = ans + (k - day[i]) + 1
				else:
					ans = ans + 2 + (k - day[i] - 1) * 2
			elif day[i] == day[i - 1] == day[(i + 1) % n]:
				if k == 0:
					ans = ans + l[i]
					continue
				ans = ans + l[i] + k * 2
			elif day[(i + 1) % n] == day[i] or day[i - 1] == day[i]:
				ans = ans + l[i]
				if k == 1:
					ans = ans + 1
				if k > 1:
					ans = ans + (k - 1) * 2 + 1
			else:
				if k == 0:
					ans = ans + l[i]
					continue
				ans = ans + l[i] + (k - 1) * 2
	print(ans)


import sys
import bisect
input = lambda : sys.stdin.readline().strip()
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	non_zero = []
	for i in range(n):
		if a[i] != 0:
			non_zero.append(i)
	if len(non_zero) == 0:
		print(0)
		continue
	first = [k] * n
	k_ = 0
	while k_ < k and len(non_zero):
		new_non_zero = []
		for i in non_zero:
			if a[(i - 1) % n] and a[(i + 1) % n]:
				a[(i - 1) % n] += 1
				a[(i + 1) % n] += 1
				first[i] = k_ + 1
			elif a[(i - 1) % n]:
				a[(i - 1) % n] += 1
				a[(i + 1) % n] += 1
				new_non_zero.append(i)
				new_non_zero.append((i + 1) % n)
			elif a[(i + 1) % n]:
				a[(i + 1) % n] += 1
				a[(i - 1) % n] += 1
				new_non_zero.append(i)
				new_non_zero.append((i - 1) % n)
			else:
				a[(i + 1) % n] += 1
				a[(i - 1) % n] += 1
				new_non_zero.append(i)
				new_non_zero.append((i - 1) % n)
				new_non_zero.append((i + 1) % n)
		non_zero = new_non_zero
		k_ += 1
	ans = sum(a)
	for i in range(n):
		ans += 2 * (k - first[i])
	print(ans)


for india in range(int(input())):
	(N, K) = map(int, input().split())
	li = list(map(int, input().split()))
	result = sum(li)
	if result == 0 or K == 0:
		print(result)
		continue
	position = -1
	leftist = [0 for i in range(N)]
	rightist = [0 for i in range(N)]
	while li[N + position] == 0:
		position -= 1
	for i in range(N):
		leftist[i] = i - position
		if li[i]:
			position = i
	position = N
	while li[position - N] == 0:
		position += 1
	for i in range(N - 1, -1, -1):
		rightist[i] = position - i
		if li[i]:
			position = i
	for i in range(N):
		if li[i]:
			if leftist[i] == 1:
				result -= -K
			else:
				result += K - 1
			if rightist[i] == 1:
				result -= -K
			else:
				result += K - 1
		else:
			sec = min(leftist[i], rightist[i])
			if leftist[i] < rightist[i]:
				result += max(0, K - sec + 1)
				result += max(0, K - min(sec + 1, rightist[i] - 1))
			else:
				result += max(0, K - sec + 1)
				result += max(0, K - min(sec + 1, leftist[i] - 1))
	print(result)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	nlist = list(map(int, input().split()))
	x = k
	y = 0
	ans = 0
	nlist1 = [j for j in nlist]
	while x != 0:
		c = 0
		for j in range(n):
			if nlist[j] == 0:
				c += 1
			if nlist[j] > 0 and j > 0 and (j < n - 1):
				nlist1[j - 1] += 1
				nlist1[j + 1] += 1
			elif j == n - 1 and nlist[j] > 0:
				nlist1[j - 1] += 1
				nlist1[0] += 1
			elif j == 0 and nlist[j] > 0:
				nlist1[n - 1] += 1
				nlist1[j + 1] += 1
		x -= 1
		for j in range(n):
			nlist[j] = nlist1[j]
		if c == n:
			y = 1
			break
		if c == 0:
			break
	if y == 1:
		print('0')
		continue
	if x > 0:
		print(sum(nlist) + x * 2 * n)
	if x == 0:
		print(sum(nlist))


import sys
from collections import deque
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def MEX(st, maxi):
	for i in range(1, maxi):
		if i not in st:
			return i

def ans():
	(n, k) = ari()
	arr = ari()
	if k == 0:
		return sum(arr)
	if arr.count(0) == n:
		return 0
	for j in range(k):
		pos = []
		lock = False
		for i in range(n):
			if arr[i] != 0:
				pos.append((i + 1) % n)
				pos.append(i - 1)
			if arr[i] == 0:
				lock = True
		if lock == False:
			break
		else:
			for it in pos:
				arr[it] += 1
	if lock == False:
		ok = k - j
		ok = ok * 2 * n
		loca = sum(arr) + ok
	else:
		loca = sum(arr)
	return loca
for _ in range(test_case):
	print(ans())


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	res = sum(l)
	if res == 0 or k == 0:
		print(res)
		continue
	pos = -1
	lef = [0 for i in range(n)]
	rig = [0 for i in range(n)]
	while l[n + pos] == 0:
		pos = pos - 1
	for i in range(n):
		lef[i] = i - pos
		if l[i]:
			pos = i
	pos = n
	while l[pos - n] == 0:
		pos = pos + 1
	for i in range(n - 1, -1, -1):
		rig[i] = pos - i
		if l[i]:
			pos = i
	for i in range(n):
		if l[i]:
			if lef[i] == 1:
				res -= -k
			else:
				res += k - 1
			if rig[i] == 1:
				res -= -k
			else:
				res += k - 1
		else:
			sec = min(lef[i], rig[i])
			if lef[i] < rig[i]:
				res += max(0, k - sec + 1)
				res += max(0, k - min(sec + 1, rig[i] - 1))
			else:
				res += max(0, k - sec + 1)
				res += max(0, k - min(sec + 1, lef[i] - 1))
	print(res)


def main():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sum = 0
	map_ = {}
	for i in range(n):
		if arr[i] != 0:
			sum += arr[i]
			map_[i] = 1
	if k == 0 or sum == 0:
		return sum
	check = len(map_)
	while check < n:
		sum += len(map_) * 2
		k -= 1
		if k == 0:
			return sum
		list_ = []
		for key in map_:
			if key == 0:
				if 1 not in map_:
					list_.append(1)
				if n - 1 not in map_:
					list_.append(n - 1)
			elif key == n - 1:
				if n - 2 not in map_:
					list_.append(n - 2)
				if 0 not in map_:
					list_.append(0)
			else:
				if key + 1 not in map_:
					list_.append(key + 1)
				if key - 1 not in map_:
					list_.append(key - 1)
		for e in list_:
			map_[e] = 1
		check = len(map_)
	sum += k * n * 2
	return sum
t = int(input())
for i in range(t):
	print(main())


def fun(n, x, l):
	c = 0
	c1 = 0
	y = 0
	s = sum(l)
	s1 = 0
	p = 0
	for i in range(n):
		if l[i] > 0:
			p += 1
	if x == 0:
		print(s)
	elif p == 0:
		print(s)
	else:
		while c < n:
			c = 0
			l1 = []
			s = sum(l)
			for i in range(n):
				if l[i] > 0:
					l1.append(i)
					c += 1
			for i in l1:
				if i == 0:
					l[i + 1] += 1
					l[-1] += 1
				elif i == n - 1:
					l[i - 1] += 1
					l[0] += 1
				else:
					l[i - 1] += 1
					l[i + 1] += 1
			c1 += 1
			s1 = sum(l)
			if c1 == x:
				y += 1
				break
		z = s1 - s
		if y == 1:
			print(s1)
		else:
			print((x - c1) * z + s1)
for test in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	fun(n, x, l)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	while k:
		o = []
		for j in range(n):
			if l[j] > 0:
				o.append(j)
		if len(o) == 0 or len(o) == n:
			break
		for h in o:
			l[h - 1] += 1
			if h == n - 1:
				l[0] += 1
			else:
				l[h + 1] += 1
		k = k - 1
	if sum(l) == 0:
		print(0)
	elif k > 0:
		print(2 * n * k + sum(l))
	else:
		print(sum(l))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if arr.count(0) == n:
		print(0)
		continue
	while arr.count(0) != 0 and k != 0:
		arr = [arr[i] + bool(arr[(i + 1) % n]) + bool(arr[(i - 1) % n]) for i in range(n)]
		k -= 1
	answer = sum(arr)
	answer += 2 * n * k
	print(answer)


for _ in range(int(input())):
	(N, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	gz = {}
	for j in range(N):
		if a[j] > 0:
			gz[j] = (j - 1 if j > 0 else N - 1, j + 1 if j < N - 1 else 0)
	for i in range(k):
		t = {}
		inc = 0
		for j in gz:
			p = gz[j][0]
			n = gz[j][1]
			a[p] += 1
			a[n] += 1
			inc += 2
			if not p in gz:
				t[p] = (p - 1 if p > 0 else N - 1, p + 1 if p < N - 1 else 0)
			if not n in gz:
				t[n] = (n - 1 if n > 0 else N - 1, n + 1 if n < N - 1 else 0)
		if len(t) == 0:
			break
		gz.update(t)
	s = sum(a)
	if not k == 0:
		s += inc * (k - i - 1)
	print(s)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	if len(list(filter(lambda x: x > 0, A))) == 0:
		print(0)
	else:
		temp = A.copy()
		while 0 in temp and K:
			for i in range(N):
				if A[i] > 0:
					temp[i - 1] += 1
					try:
						temp[i + 1] += 1
					except:
						temp[0] += 1
			K -= 1
			A = temp.copy()
		if K > 0:
			print(sum(A) + len(A) * K * 2)
		else:
			print(sum(A))


from collections import deque
test = int(input())
for t in range(test):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	dq = set([i for i in range(n) if a[i] > 0])
	while 0 < len(dq) < n and k > 0:
		k -= 1
		sz = len(dq)
		p = set()
		for i in range(sz):
			index = dq.pop()
			l = n - 1 if index == 0 else index - 1
			r = 0 if index + 1 >= n else index + 1
			a[l] += 1
			a[r] += 1
			p.add(index)
			p.add(r)
			p.add(l)
		dq = p
	if len(dq) > 0:
		for i in range(n):
			a[i] += 2 * max(k, 0)
	print(sum(a))


testc = int(input())
for x in range(testc):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = l.count(0)
	if c == n:
		print(0)
		continue
	while k > 0:
		if c == 0:
			break
		m = []
		k = k - 1
		for j in range(n):
			if l[j] > 0:
				m.append(j)
		for j in m:
			if j - 1 >= 0:
				if l[j - 1] == 0:
					c = c - 1
				l[j - 1] += 1
			if j + 1 < n:
				if l[j + 1] == 0:
					c = c - 1
				l[j + 1] += 1
			if j == n - 1:
				if l[0] == 0:
					c = c - 1
				l[0] += 1
			if j == 0:
				if l[n - 1] == 0:
					c = c - 1
				l[n - 1] += 1
	print(sum(l) + n * k * 2)


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	if sum(b) == 0:
		print(0)
		continue
	c = []
	d = []
	for j in range(a[0]):
		if b[j] != 0:
			c.append(j)
	k = 0
	for j in range(a[0]):
		if k >= len(c):
			d.append(-1)
			continue
		if j <= c[k]:
			d.append(c[k] - j)
		else:
			k += 1
			if k < len(c):
				d.append(c[k] - j)
			else:
				d.append(-1)
	k = len(c) - 1
	for j in range(a[0] - 1, -1, -1):
		if k >= 0:
			if j >= c[k]:
				if d[j] == -1:
					d[j] = j - c[k]
				else:
					d[j] = min(d[j], j - c[k])
			else:
				k -= 1
				if k >= 0:
					if d[j] == -1:
						d[j] = j - c[k]
					else:
						d[j] = min(d[j], j - c[k])
	for j in range(c[0]):
		d[j] = min(d[j], j + a[0] - c[-1])
	for j in range(c[-1], a[0]):
		d[j] = min(d[j], c[0] + a[0] - j)
	s = sum(b)
	for k in range(a[0]):
		if a[1] >= d[k]:
			s += 2 * (a[1] - d[k])
	print(s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	s = set()
	p = []
	for i in range(n):
		if l[i] > 0:
			ans += l[i]
			s.add(i)
			p.append(i)
	if not s:
		print(ans)
	else:
		xx = len(s)
		while xx < n and k:
			ans += 2 * xx
			k -= 1
			x = []
			for ele in p:
				u = ele + 1
				d = ele - 1
				if u >= n:
					u = 0
				if d < 0:
					d = n - 1
				if u not in s:
					s.add(u)
					x.append(u)
					xx += 1
				if d not in s:
					s.add(d)
					x.append(d)
					xx += 1
			p = x
		if k:
			ans += 2 * xx * k
		print(ans)


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	s = sum(a)
	if s == 0:
		print(0)
	else:
		a2 = [1000000000] * n
		a3 = [1000000000] * n
		stack = []
		c = 0
		for i in range(n):
			if a[i] > 0:
				stack.append(i)
				c = c + 1
			elif not stack == []:
				a2[i] = i - stack[-1]
			else:
				continue
		stack[-1] = stack[-1] - n
		for i in range(n):
			if a[i] > 0:
				break
			elif not stack == []:
				if a2[i] == 1000000000:
					a2[i] = i - stack[-1]
		stack = []
		for i in range(n - 1, -1, -1):
			if a[i] > 0:
				stack.append(i)
			elif not stack == []:
				a3[i] = stack[-1] - i
			else:
				continue
		stack[-1] = n + stack[-1]
		for i in range(n - 1, -1, -1):
			if a[i] > 0:
				break
			elif not stack == []:
				if a3[i] == 1000000000:
					a3[i] = stack[-1] - i
		ma = 0
		d = {}
		for i in range(n):
			sss = min(a3[i], a2[i])
			if sss == 1000000000:
				continue
			if sss not in d:
				d[sss] = 1
			else:
				d[sss] = d[sss] + 1
			if sss > ma and sss != 1000000000:
				ma = sss
		if k > ma:
			for i in range(1, ma + 1):
				s = s + 2 * c
				if i in d.keys():
					c = c + d[i]
			s = s + (k - ma) * 2 * c
		else:
			for i in range(1, k + 1):
				s = s + 2 * c
				if i in d.keys():
					c = c + d[i]
		print(s)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(n, k) = get_ints()
	a = get_array()
	arr = [-1 for i in range(n)]
	for i in range(n):
		if a[i] > 0:
			arr[i] = i
		elif i - 1 >= 0:
			arr[i] = arr[i - 1]
	arr1 = [-1 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if a[i] > 0:
			arr1[i] = i
		elif i + 1 < n:
			arr1[i] = arr1[i + 1]
	arr2 = [inf for i in range(n)]
	for i in range(n):
		if a[i] > 0:
			arr2[i] = 0
		else:
			if arr[i] >= 0:
				arr2[i] = min(arr2[i], i - arr[i])
			if arr[n - 1] >= 0:
				arr2[i] = min(n - arr[n - 1] + i, arr2[i])
			if arr1[i] >= 0:
				arr2[i] = min(arr2[i], arr1[i] - i)
			if arr1[0] >= 0:
				arr2[i] = min(arr2[i], arr1[0] + n - i)
	ans = 0
	for i in range(n):
		if a[i] > 0:
			ans += a[i]
		ans += max(0, k - arr2[(i - 1) % n])
		ans += max(0, k - arr2[(i + 1) % n])
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = sum(arr)
	if ans == 0:
		print(0)
	elif arr.count(0) == 0:
		print(ans + 2 * n * k)
	else:
		temp = arr.copy()
		flag = 0
		for j in range(k):
			diff = 0
			for i in range(n):
				if arr[i] > 0:
					diff += 2
					temp[i - 1] += 1
					temp[(i + 1) % n] += 1
					ans += 2
			if diff == 2 * n:
				print(ans + (k - j - 1) * diff)
				flag = 1
				break
			arr = temp.copy()
		if flag == 0:
			print(ans)