1978F · Large Graph

Problem: Given an array $a$ of length $n$. Let's construct a square matrix $b$ of size $n \times n$, in which the $i$-th row contains the array $a$ cyclically shifted to the right by $(i - 1)$. For example, for the array $a = [3, 4, 5]$, the obtained matrix is

$b = \begin{bmatrix} 3 & 4 & 5 \\ 5 & 3 & 4 \\ 4 & 5 & 3 \end{bmatrix}$

Let's construct the following graph:

• The graph contains $n^2$ vertices, each of which corresponds to one of the elements of the matrix. Let's denote the vertex corresponding to the element $b_{i, j}$ as $(i, j)$.
• We will draw an edge between vertices $(i_1, j_1)$ and $(i_2, j_2)$ if $|i_1 - i_2| + |j_1 - j_2| \le k$ and $\gcd(b_{i_1, j_1}, b_{i_2, j_2}) > 1$, where $\gcd(x, y)$ denotes the greatest common divisor of integers $x$ and $y$.

Your task is to calculate the number of connected components$^{\dagger}$ in the obtained graph.

$^{\dagger}$A connected component of a graph is a set of vertices in which any vertex is reachable from any other via edges, and adding any other vertex to the set violates this rule.

Input Format: Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^6$, $2 \le k \le 2 \cdot 10^6$) — the length of the array and the parameter $k$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output Format: For each test case, output a single integer — the number of connected components in the obtained graph.

Note: In the first test case, the matrix $b$ is given in the statement. The first connected component contains the vertices $(1, 1)$, $(2, 2)$, and $(3, 3)$. The second connected component contains the vertices $(1, 2)$, $(2, 3)$, and $(3, 1)$. The third connected component contains the vertices $(1, 3)$, $(2, 1)$, and $(3, 2)$. Thus, the graph has $3$ connected components.

In the second test case, the following matrix is obtained:

$b = \begin{bmatrix} 3 & 4 & 9 \\ 9 & 3 & 4 \\ 4 & 9 & 3 \end{bmatrix}$

The first connected component contains all vertices corresponding to elements with values $3$ and $9$. The second connected component contains all vertices corresponding to elements with the value $4$.

In the fourth test case, all vertices are in one connected component.