import sys
input = sys.stdin.buffer.readline
n = 1000000
f = [False]*(n+1)
for i in range(2,int(n**0.5)+1):
	if f[i]: continue
	for j in range(i*2,n+1,i):
		f[j] = True
for _ in range(int(input())):
	n,e = map(int,input().split())
	a = list(map(int,input().split()))
	ans = 0
	for i in range(e):
		cnt = 0
		q = 0
		for j in range(i,n,e):
			if a[j]==1: cnt += 1
			elif f[a[j]]==False:
				ans += q*cnt+cnt
				q = cnt+1
				cnt = 0
			else:
				ans += q*cnt
				cnt = 0
				q = 0
		ans += q*cnt
	print(ans)