给定一个长度为 $$$n$$$ 的数组 $$$a$$$。让我们构造一个大小为 $$$n \times n$$$ 的方阵 $$$b$$$,其中第 $$$i$$$ 行包含数组 $$$a$$$ 循环右移 $$$(i - 1)$$$。例如,对于数组$$$a = [3, 4, 5]$$$,得到的矩阵为
$$$$$$b = \begin{bmatrix} 3 & 4 & 5 \\ 5 & 3 & 4 \\ 4 & 5 & 3 \end{bmatrix}$$$$$$
让我们构建下图:
- 该图包含 $$$n^2$$$ 个顶点,每个顶点对应于矩阵的一个元素。我们将元素 $$$b_{i, j}$$$ 对应的顶点表示为 $$$(i, j)$$$。
- 我们将在顶点 $$$(i_1, j_1)$$$ 和 $$$(i_2, j_2)$$$ 之间绘制一条边,如果 $$$|i_1 - i_2| + |j_1 - j_2| \le k$$$ 和 $$$\gcd(b_{i_1, j_1}, b_{i_2, j_2}) > 1$$$,其中 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数。
你的任务是计算所获得的图中连通分量$$$^{\dagger}$$$的数量。
$$$^{\dagger}$$$图的连通分量是一组顶点,其中任何顶点都可以从任何其他通过边到达,并且将任何其他顶点添加到该集合中都会违反此规则。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$2 \le k \le 2 \cdot 10^6$$$) — 数组和参数 $$$k$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出一个整数 - 所获得的图中连接分量的数量。
示例
输入 #1
6 3 3 3 4 5 3 3 3 4 9 3 2 3 4 9 2 2 2 8 5 3 8 27 5 4 3 4 10 2 2 2 2
输出 #1
3 2 3 1 4 1
注意
在第一个测试用例中,语句中给出了矩阵 $$$b$$$。第一个连通分量包含顶点 $$$(1, 1)$$$、$$$(2, 2)$$$ 和 $$$(3, 3)$$$。第二个连通分量包含顶点 $$$(1, 2)$$$、$$$(2, 3)$$$ 和 $$$(3, 1)$$$。第三个连通分量包含顶点 $$$(1, 3)$$$、$$$(2, 1)$$$ 和 $$$(3, 2)$$$。因此,该图有 $$$3$$$ 个连通分量。
在第二个测试用例中,得到以下矩阵:
$$$$$$b = \begin{bmatrix} 3 & 4 & 9 \\ 9 & 3 & 4 \\ 4 & 9 & 3 \end{bmatrix}$$$$$$
第一个连通分量包含与值为 $$$3$$$ 和 $$$9$$$ 的元素对应的所有顶点。第二个连通分量包含与值为 $$$4$$$ 的元素对应的所有顶点。
在第四个测试用例中,所有顶点都在一个连接组件中。