在进行复杂的市场分析时,William 遇到了以下问题:
对于给定的大小为 $$$n$$$ 的数组 $$$a$$$ 和自然数 $$$e$$$,计算满足以下条件的自然数对 $$$(i, k)$$$ 的数量:
- $$$1 \le i, k$$$
- $$$i + e \cdot k \le n$$$。
- 产品 $$$a_i \cdot a_{i + e} \cdot a_{i + 2 \cdot e} \cdot \ldots \cdot a_{i + k \cdot e} $$$ 是素数。
素数(或质数)是大于 1 的自然数,且不是两个较小自然数的乘积。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$e$$$ $$$(1 \le e \le n \le 2 \cdot 10^5)$$$,分别表示数组中的项目数和数量 $$$e$$$。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 10^6)$$$,即数组的内容。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,按以下格式输出答案:
输出一行,包含满足条件的数字$$$(i, k)$$$的个数。
示例
输入 #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
注意
在第一个示例测试用例中,两对满足条件:
1. $$$i = 2, k = 1$$$,其乘积为:$$$a_{2} \cdot a_{5} = 2$$$,这是一个质数。
2. $$$i = 3, k = 1$$$,其乘积为:$$$a_{3} \cdot a_{6} = 19$$$,这是一个素数。
在第二个示例测试用例中,没有满足条件的对。
在第三个示例测试用例中,四对满足条件:
1. $$$i = 1, k = 1$$$,其乘积为:$$$a_{1} \cdot a_{4} = 2$$$,这是一个素数。
2. $$$i = 1, k = 2$$$,其乘积为: $$$a_{1} \cdot a_{4} \cdot a_{7} = 2$$$,这是一个素数。
3. $$$i = 3, k = 1$$$,其乘积为:$$$a_{3} \cdot a_{6} = 2$$$,这是一个素数。
4. $$$i = 6, k = 1$$$,其乘积为:$$$a_{6} \cdot a_{9} = 2$$$,这是一个素数。
在第四个示例测试用例中,没有满足条件的对。
在第五个示例测试用例中,有五对满足条件:
1. $$$i = 1, k = 1$$$,其乘积为:$$$a_{1} \cdot a_{2} = 2$$$,这是一个素数。
2. $$$i = 1, k = 2$$$,其乘积为: $$$a_{1} \cdot a_{2} \cdot a_{3} = 2$$$,这是一个质数。
3. $$$i = 1, k = 3$$$,其乘积为: $$$a_{1} \cdot a_{2} \cdot a_{3} \cdot a_{4} = 2$$$,这是一个素数。
4. $$$i = 2, k = 1$$$,其乘积为:$$$a_{2} \cdot a_{3} = 2$$$,这是一个质数。
5. $$$i = 2, k = 2$$$,其乘积为: $$$a_{2} \cdot a_{3} \cdot a_{4} = 2$$$,这是一个质数。
在第六个示例测试用例中,没有满足条件的对。