Complex Market Analysis solution codeforces

Complex Market Analysis solution codeforces

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:

  • 1i,k1≤i,k
  • i+ekni+e⋅k≤n.
  • Product aiai+eai+2eai+keai⋅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.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t100001≤t≤10000). Description of the test cases follows.

The first line of each test case contains two integers nn and ee (1en2105)(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 (1ai106)(1≤ai≤106), the contents of the array.

It is guaranteed that the sum of nn over all test cases does not exceed 21052⋅105.

Output

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.

Example
input

Copy
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

Copy
2
0
4
0
5
0
Note

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

  1. i=2,k=1i=2,k=1, for which the product is: a2a5=2a2⋅a5=2 which is a prime number.
  2. i=3,k=1i=3,k=1, for which the product is: a3a6=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:

  1. i=1,k=1i=1,k=1, for which the product is: a1a4=2a1⋅a4=2 which is a prime number.
  2. i=1,k=2i=1,k=2, for which the product is: a1a4a7=2a1⋅a4⋅a7=2 which is a prime number.
  3. i=3,k=1i=3,k=1, for which the product is: a3a6=2a3⋅a6=2 which is a prime number.
  4. i=6,k=1i=6,k=1, for which the product is: a6a9=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:

  1. i=1,k=1i=1,k=1, for which the product is: a1a2=2a1⋅a2=2 which is a prime number.
  2. i=1,k=2i=1,k=2, for which the product is: a1a2a3=2a1⋅a2⋅a3=2 which is a prime number.
  3. i=1,k=3i=1,k=3, for which the product is: a1a2a3a4=2a1⋅a2⋅a3⋅a4=2 which is a prime number.
  4. i=2,k=1i=2,k=1, for which the product is: a2a3=2a2⋅a3=2 which is a prime number.
  5. i=2,k=2i=2,k=2, for which the product is: a2a3a4=2a2⋅a3⋅a4=2 which is a prime number.

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

Leave a Comment

Your email address will not be published. Required fields are marked *