Contents
Complex Market Analysis solution codeforces

For Solution
Click Here!
While performing complex market analysis William encountered the following problem:
For a given array aa of size nn and a natural number ee, calculate the number of pairs of natural numbers (i,k)(i,k) which satisfy the following conditions:
 1≤i,k1≤i,k
 i+e⋅k≤ni+e⋅k≤n.
 Product ai⋅ai+e⋅ai+2⋅e⋅…⋅ai+k⋅eai⋅ai+e⋅ai+2⋅e⋅…⋅ai+k⋅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.
Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤100001≤t≤10000). Description of the test cases follows.
The first line of each test case contains two integers nn and ee (1≤e≤n≤2⋅105)(1≤e≤n≤2⋅105), the number of items in the array and number ee, respectively.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤106)(1≤ai≤106), the contents of the array.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
For each test case output the answer in the following format:
Output one line containing the number of pairs of numbers (i,k)(i,k) which satisfy the conditions.
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
2 0 4 0 5 0
In the first example test case two pairs satisfy the conditions:
 i=2,k=1i=2,k=1, for which the product is: a2⋅a5=2a2⋅a5=2 which is a prime number.
 i=3,k=1i=3,k=1, for which the product is: a3⋅a6=19a3⋅a6=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=1i=1,k=1, for which the product is: a1⋅a4=2a1⋅a4=2 which is a prime number.
 i=1,k=2i=1,k=2, for which the product is: a1⋅a4⋅a7=2a1⋅a4⋅a7=2 which is a prime number.
 i=3,k=1i=3,k=1, for which the product is: a3⋅a6=2a3⋅a6=2 which is a prime number.
 i=6,k=1i=6,k=1, for which the product is: a6⋅a9=2a6⋅a9=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=1i=1,k=1, for which the product is: a1⋅a2=2a1⋅a2=2 which is a prime number.
 i=1,k=2i=1,k=2, for which the product is: a1⋅a2⋅a3=2a1⋅a2⋅a3=2 which is a prime number.
 i=1,k=3i=1,k=3, for which the product is: a1⋅a2⋅a3⋅a4=2a1⋅a2⋅a3⋅a4=2 which is a prime number.
 i=2,k=1i=2,k=1, for which the product is: a2⋅a3=2a2⋅a3=2 which is a prime number.
 i=2,k=2i=2,k=2, for which the product is: a2⋅a3⋅a4=2a2⋅a3⋅a4=2 which is a prime number.
In the sixth example test case there are no pairs that satisfy the conditions.

For Solution
Click Here!