While performing complex market analysis William encountered the following problem:

For a given array $a$ of size $n$ and a natural number $e$, calculate the number of pairs of natural numbers $(i, k)$ which satisfy the following conditions:

$1 \le i, k$

$i + e \cdot k \le n$.

Product $a_i \cdot a_{i + e} \cdot a_{i + 2 \cdot e} \cdot \ldots \cdot a_{i + k \cdot e} $ is a prime number.

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10000$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $e$ $(1 \le e \le n \le 2 \cdot 10^5)$, the number of items in the array and number $e$, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^6)$, the contents of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case output the answer in the following format:

Output one line containing the number of pairs of numbers $(i, k)$ which satisfy the conditions.


-----Examples-----

Input
6
7 3
10 2 1 3 1 19 3
3 2
1 13 1
9 3
2 4 2 1 1 1 1 4 2
3 1
1 1 1
4 1
1 2 1 1
2 2
1 2
Output
2
0
4
0
5
0


-----Note-----

In the first example test case two pairs satisfy the conditions:

$i = 2, k = 1$, for which the product is: $a_{2} \cdot a_{5} = 2$ which is a prime number.

$i = 3, k = 1$, for which the product is: $a_{3} \cdot a_{6} = 19$ which is a prime number.

In the second example test case there are no pairs that satisfy the conditions.

In the third example test case four pairs satisfy the conditions:

$i = 1, k = 1$, for which the product is: $a_{1} \cdot a_{4} = 2$ which is a prime number.

$i = 1, k = 2$, for which the product is: $a_{1} \cdot a_{4} \cdot a_{7} = 2$ which is a prime number.

$i = 3, k = 1$, for which the product is: $a_{3} \cdot a_{6} = 2$ which is a prime number.

$i = 6, k = 1$, for which the product is: $a_{6} \cdot a_{9} = 2$ which is a prime number.

In the fourth example test case there are no pairs that satisfy the conditions.

In the fifth example test case five pairs satisfy the conditions:

$i = 1, k = 1$, for which the product is: $a_{1} \cdot a_{2} = 2$ which is a prime number.

$i = 1, k = 2$, for which the product is: $a_{1} \cdot a_{2} \cdot a_{3} = 2$ which is a prime number.

$i = 1, k = 3$, for which the product is: $a_{1} \cdot a_{2} \cdot a_{3} \cdot a_{4} = 2$ which is a prime number.

$i = 2, k = 1$, for which the product is: $a_{2} \cdot a_{3} = 2$ which is a prime number.

$i = 2, k = 2$, for which the product is: $a_{2} \cdot a_{3} \cdot a_{4} = 2$ which is a prime number.

In the sixth example test case there are no pairs that satisfy the conditions.

Source: codeforces | Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Implementation

Number theory

Dynamic programming


Solutions:
import sys
isPrime = [True] * int(1000000.0 + 2)

def solve():
	inp = sys.stdin.readline
	(n, e) = map(int, inp().split())
	a = list(map(int, inp().split()))
	w = [True] * n
	r = 0
	for i in range(n):
		if w[i]:
			j = 0
			z = i
			last = -1
			last1 = -1
			p = False
			while z < n:
				w[z] = False
				v = a[z]
				if v > 1:
					(last, last1) = (j, last)
					p = isPrime[v]
					if p:
						r -= 1
				if p:
					r += last - last1
				z += e
				j += 1
	print(r)

def main():
	M = len(isPrime)
	isPrime[1] = False
	isPrime[0] = False
	i = 2
	while i * i < M:
		if isPrime[i]:
			j = i * i
			while j < M:
				isPrime[j] = False
				j += i
		i += 1
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from sys import stdin
input = stdin.readline
n = 10 ** 6
prime = [True for i in range(n + 1)]
prime[1] = False
p = 2
while p * p <= n:
	if prime[p] == True:
		for i in range(p * p, n + 1, p):
			prime[i] = False
	p += 1
for _ in range(int(input())):
	(n, b) = map(int, input().split())
	li = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if prime[li[i]] == True:
			(j, c) = (i + b, 0)
			while j < n and li[j] == 1:
				(j, c) = (j + b, c + 1)
			(d, j) = (0, i - b)
			while j >= 0 and li[j] == 1:
				(j, d) = (j - b, d + 1)
			ans = ans + c + d * (c + 1)
	print(ans)


from sys import stdin
p = 2
isprime = [True] * (10 ** 6 + 1)
isprime[0] = isprime[1] = False
while p * p <= 10 ** 6:
	if isprime[p]:
		for i in range(p * p, 10 ** 6 + 1, p):
			isprime[i] = False
	p += 1
for _ in range(int(stdin.readline())):
	(n, e) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	onesahead = [0 for i in range(n)]
	onesbefore = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if arr[i] == 1:
			onesahead[i] = 1
			if i + e < n:
				onesahead[i] += onesahead[i + e]
	for i in range(0, n):
		if arr[i] == 1:
			onesbefore[i] = 1
			if i - e >= 0:
				onesbefore[i] += onesbefore[i - e]
	ans = 0
	for i in range(n):
		if isprime[arr[i]]:
			a = 0
			b = 0
			if i + e < n:
				a = onesahead[i + e]
			if i - e >= 0:
				b = onesbefore[i - e]
				b = b * (a + 1)
			nn = a + b
			3
			ans += nn
	print(ans)


n = 10 ** 6
prime = [True for i in range(n + 1)]
prime[1] = False
p = 2
while p <= 1000:
	if prime[p]:
		for i in range(p * p, n + 1, p):
			prime[i] = False
	p += 1
t = int(input())
for _ in range(t):
	(n, e) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(e):
		j = i
		left = 0
		right = 0
		while j < n:
			if arr[j] == 1:
				left += 1
				j += e
				continue
			if prime[arr[j]]:
				j += e
				while j < n and arr[j] == 1:
					right += 1
					j += e
				ans += left + right + left * right
				left = right
				right = 0
			else:
				left = 0
				j += e
	print(ans)


prime = [1 for i in range(1000002)]
p = 2
(prime[0], prime[1]) = (0, 0)
while p * p <= 1000001:
	if prime[p]:
		for i in range(p * p, 1000002, p):
			prime[i] = 0
	p += 1
for _ in range(int(input())):
	(n, e) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		if prime[arr[i]]:
			j = i + e
			c = 0
			while j < n and arr[j] == 1:
				c += 1
				j += e
			j = i - e
			d = 0
			while j >= 0 and arr[j] == 1:
				d += 1
				j -= e
			ans = ans + c + (c + 1) * d
	print(ans)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
prime = [1 for i in range(1000002)]
p = 2
while p * p <= 1000001:
	if prime[p]:
		for i in range(p * p, 1000002, p):
			prime[i] = 0
	p += 1
for _ in range(I()):
	(n, e) = M()
	a = L()
	ans = 0
	for i in range(n):
		if a[i] > 1 and prime[a[i]]:
			j = i - e
			d1 = d2 = 0
			while j >= 0 and a[j] == 1:
				j -= e
				d1 += 1
			k = i + e
			while k < n and a[k] == 1:
				k += e
				d2 += 1
			ans += d1 * d2 + d1 + d2
	print(ans)


def SieveOfEratosthenes(n):
	li = [1] * (n + 1)
	p = 2
	while p * p <= n:
		if li[p] == 1:
			for i in range(p ** 2, n + 1, p):
				li[i] = 0
		p += 1
	li[0] = 0
	li[1] = 0
	return li
li = SieveOfEratosthenes(10 ** 6 + 1)
t = int(input())
for i in range(t):
	(n, e) = map(int, input().split())
	a = list(map(int, input().split()))
	lipr = []
	c = 0
	for i in range(n):
		if li[a[i]] == 1:
			lipr.append(i)
	c = 0
	le = len(lipr)
	for i in range(le):
		lc = 0
		rc = 0
		for j in range(lipr[i] + e, n, e):
			if a[j] == 1:
				lc += 1
			else:
				break
		for j in range(lipr[i] - e, -1, -e):
			if a[j] == 1:
				rc += 1
			else:
				break
		c += rc
		c += lc
		c += rc * lc
	print(c)


isPrime = [1 for j in range(1000003)]

def sieve(isPrime):
	maxN = 1000002
	(isPrime[0], isPrime[1]) = (0, 0)
	i = 2
	while i * i <= maxN:
		if isPrime[i]:
			for j in range(i * i, maxN + 1, i):
				isPrime[j] = 0
		i += 1
sieve(isPrime)
for i in range(int(input())):
	(n, e) = map(int, input().split())
	a = [int(j) for j in input().split()]
	ans = 0
	for j in range(len(a)):
		if a[j] == 1 or isPrime[a[j]]:
			(x, y) = (0, 0)
			(k, cnt) = (0, 0)
			while j + k * e < n:
				if a[j + k * e] == 1:
					if cnt == 0:
						a[j + k * e] = -1
						x += 1
					else:
						y += 1
					k += 1
				elif cnt == 0 and isPrime[a[j + k * e]]:
					a[j + k * e] = -1
					cnt += 1
					x += 1
					k += 1
				else:
					break
			if k == 1:
				ans += 0
			elif y != 0:
				ans += (x - 1) * (y + 1) + y
			elif x > 1 and cnt != 0:
				ans += x - 1
	print(ans)


def soe(n):
	s = set()
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			s.add(p)
	return s
s = soe(10 ** 6)

def count(cnt1, cnt2):
	return (cnt1 - 1) * (cnt2 - 1)
for _ in range(int(input())):
	(n, e) = map(int, input().split())
	a = list(map(int, input().split()))
	pa = [0] * n
	ons = [0] * n
	vis = [0] * n
	for i in range(n):
		if a[i] == 1:
			ons[i] = 1
		elif a[i] in s:
			pa[i] = 1
	ans = 0
	i = 0
	while i < n:
		if pa[i] == 1:
			j = i + e
			cnt1 = 1
			while j < n:
				if ons[j] == 1:
					cnt1 += 1
					vis[j] = 1
				else:
					break
				j += e
			j = i - e
			cnt2 = 1
			while j >= 0:
				if ons[j] == 1:
					cnt2 += 1
					vis[j] = 1
				else:
					break
				j -= e
			if cnt1 + cnt2 > 2:
				ans += count(cnt1, cnt2) + cnt1 + cnt2 - 2
			i += 1
		else:
			i += 1
	print(ans)


def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	m = {}
	for p in range(2, n):
		if prime[p]:
			m[p] = 1
	return m
h = SieveOfEratosthenes(10 ** 6)
a = int(input())
for x in range(a):
	(b, c) = map(int, input().split())
	d = list(map(int, input().split()))
	f = 0
	for y in range(b):
		n = 0
		p = 0
		if h.get(d[y]) != None:
			for z in range(y + c, b, c):
				if d[z] == 1:
					n += 1
				else:
					break
			for z in range(y - c, -1, -c):
				if d[z] == 1:
					p += 1
				else:
					break
		f += n + p * (n + 1)
	print(f)


import sys
input = sys.stdin.readline
n = 10 ** 6
is_prime = [True for i in range(n + 1)]
is_prime[1] = False
p = 2
while p * p <= n:
	if is_prime[p]:
		for i in range(p * p, n + 1, p):
			is_prime[i] = False
	p += 1
t = int(input())
for _ in range(t):
	(n, e) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		(l, r) = (0, 0)
		if is_prime[a[i]] and a[i] != 1:
			for j in range(i + e, n, e):
				if a[j] == 1:
					r += 1
				else:
					break
			for j in range(i - e, -1, -e):
				if a[j] == 1:
					l += 1
				else:
					break
		ans += l + r + l * r
	print(ans)


import sys

def fprime():
	taille = 10 ** 6 + 1
	primes = [True for x in range(taille)]
	primes[0] = False
	primes[1] = False
	for i in range(2, taille):
		if primes[i]:
			j = 2 * i
			while j < taille:
				primes[j] = False
				j += i
	return primes

def main():
	input = sys.stdin.readline
	t = int(input())
	primes = fprime()
	for _ in range(t):
		(n, e) = map(int, input().split())
		a = list(map(int, input().split()))
		nbUn = [0 for i in range(n)]
		for i in range(n - 1, -1, -1):
			if a[i] == 1:
				if i < n - e:
					nbUn[i] = nbUn[i + e] + 1
				else:
					nbUn[i] = 1
			else:
				nbUn[i] = 0
		nbSol = [0 for i in range(n)]
		for i in range(n - 1, -1, -1):
			if a[i] != 1 and i < n - e and (nbUn[i + e] > 0):
				if primes[a[i]]:
					nbSol[i] = nbUn[i + e]
			if a[i] == 1 and i < n - e:
				if a[i + e] == 1:
					nbSol[i] = nbSol[i + e]
				elif primes[a[i + e]]:
					nbSol[i] = nbSol[i + e] + 1
		print(sum(nbSol))
main()


max = 10 ** 6 + 1
allPrime = [True] * max
allPrime[0] = allPrime[1] = False
for i in range(2, max):
	if allPrime[i]:
		for j in range(i, max, i):
			if j != i:
				allPrime[j] = False
test = int(input())
for t in range(test):
	(n, e) = map(int, input().split())
	array = list(map(int, input().split()))[:n]
	noOfOnesLeft = [0] * n
	noOfOnesRight = [0] * n
	ans = 0
	for i in range(n - 1, e - 1, -1):
		if array[i] == 1:
			noOfOnesLeft[i - e] = noOfOnesLeft[i] + 1
	for i in range(n - e):
		if array[i] == 1:
			noOfOnesRight[i + e] = noOfOnesRight[i] + 1
	for i in range(n):
		if allPrime[array[i]]:
			ans += noOfOnesLeft[i] + noOfOnesRight[i] * (noOfOnesLeft[i] + 1)
	print(ans)


primes = []
d = list(range(10 ** 6 + 1))
for i in range(2, 10 ** 6 + 1):
	if d[i] == i:
		primes.append(i)
	for j in primes:
		if i * j > 10 ** 6:
			break
		if j > d[i]:
			break
		d[i * j] = j
for _ in ' ' * int(input()):
	(n, e) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(e):
		la = a[i::e]
		delims = [i for (i, v) in enumerate(la) if v != 1]
		for (i, v) in enumerate(delims):
			u = delims[i - 1] + 1 if i else 0
			w = delims[i + 1] - 1 if i < len(delims) - 1 else len(la) - 1
			if d[la[v]] == la[v]:
				ans += (v - u + 1) * (w - v + 1) - 1
	print(ans)


p = [1 for i in range(10 ** 6 + 1)]
p[0] = 0
p[1] = 0
for i in range(2, len(p)):
	if p[i] == 1:
		for j in range(i * 2, len(p), i):
			if j % i == 0:
				p[j] = 0
t = int(input())
for test in range(t):
	(n, e) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	b = []
	for j in range(e):
		b.append([a[i] for i in range(j, len(a), e)])
	ans = 0
	for j in range(len(b)):
		for i in range(len(b[j])):
			if p[b[j][i]] == 1:
				l = i
				r = i
				Left = True
				Right = True
				while Left == True or Right == True:
					if r + 1 < len(b[j]) and b[j][r + 1] == 1:
						r += 1
					else:
						Right = False
					if l - 1 >= 0 and b[j][l - 1] == 1:
						l -= 1
					else:
						Left = False
				ans += r - i + (i - l)
				ans += (r - i) * (i - l)
	print(ans)