Дан массив \(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}\)Компонента связности графа — это множество некоторых вершин графа, в котором любая вершина достижима из любой по рёбрам, и добавление любой другой вершины в множество нарушает это правило.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество компонент связности в полученном графе.
Примечание
В первом наборе входных данных матрица \(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\).
В четвёртом наборе входных данных все вершины находятся в одной компоненте связности.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3
2
3
1
4
1
|