codeforces#P1609C. Complex Market Analysis

    ID: 32533 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>binary searchdpimplementationnumber theoryschedulestwo pointers*1400

Complex Market Analysis

Description

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 \le i, k
  • i+ekni + e \cdot k \le n.
  • Product aiai+eai+2eai+kea_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.

Each test contains multiple test cases. The first line contains the number of test cases tt (1t100001 \le t \le 10\,000). Description of the test cases follows.

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

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai106)(1 \le a_i \le 10^6), the contents of the array.

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

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.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t100001 \le t \le 10\,000). Description of the test cases follows.

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

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai106)(1 \le a_i \le 10^6), the contents of the array.

It is guaranteed that the sum of nn over all test cases does not exceed 21052 \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)(i, k) which satisfy the conditions.

Samples

输入数据 1

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

输出数据 1

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=2a_{2} \cdot a_{5} = 2 which is a prime number.
  2. i=3,k=1i = 3, k = 1, for which the product is: a3a6=19a_{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:

  1. i=1,k=1i = 1, k = 1, for which the product is: a1a4=2a_{1} \cdot a_{4} = 2 which is a prime number.
  2. i=1,k=2i = 1, k = 2, for which the product is: a1a4a7=2a_{1} \cdot a_{4} \cdot a_{7} = 2 which is a prime number.
  3. i=3,k=1i = 3, k = 1, for which the product is: a3a6=2a_{3} \cdot a_{6} = 2 which is a prime number.
  4. i=6,k=1i = 6, k = 1, for which the product is: a6a9=2a_{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:

  1. i=1,k=1i = 1, k = 1, for which the product is: a1a2=2a_{1} \cdot a_{2} = 2 which is a prime number.
  2. i=1,k=2i = 1, k = 2, for which the product is: a1a2a3=2a_{1} \cdot a_{2} \cdot a_{3} = 2 which is a prime number.
  3. i=1,k=3i = 1, k = 3, for which the product is: a1a2a3a4=2a_{1} \cdot a_{2} \cdot a_{3} \cdot a_{4} = 2 which is a prime number.
  4. i=2,k=1i = 2, k = 1, for which the product is: a2a3=2a_{2} \cdot a_{3} = 2 which is a prime number.
  5. i=2,k=2i = 2, k = 2, for which the product is: a2a3a4=2a_{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.