F. Большой граф
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$. Построим квадратную матрицу $$$b$$$ размера $$$n \times n$$$, где в $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество компонент связности в полученном графе.

Пример
Входные данные
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
Выходные данные
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$$$.

В четвёртом наборе входных данных все вершины находятся в одной компоненте связности.