В процессе сложного анализа рынка у Василия возникла следующая задача:
Дан массив $$$a$$$ длины $$$n$$$ и натуральное число $$$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} $$$ является простым числом.
Простым числом называется натуральное число больше единицы, имеющее ровно два различных натуральных делителя — единицу и самого себя.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$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)$$$.
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
2 0 4 0 5 0
В первом тестовом примере подходят две пары:
- $$$i = 2, k = 1$$$, тогда произведение: $$$a_{2} \cdot a_{5} = 2$$$ является простым числом.
- $$$i = 3, k = 1$$$, тогда произведение: $$$a_{3} \cdot a_{6} = 19$$$ является простым числом.
Во втором тестовом примере не существует подходящих пар.
В третьем тестовом примере подходят четыре пары:
- $$$i = 1, k = 1$$$, тогда произведение: $$$a_{1} \cdot a_{4} = 2$$$ является простым числом.
- $$$i = 1, k = 2$$$, тогда произведение: $$$a_{1} \cdot a_{4} \cdot a_{7} = 2$$$ является простым числом.
- $$$i = 3, k = 1$$$, тогда произведение: $$$a_{3} \cdot a_{6} = 2$$$ является простым числом.
- $$$i = 6, k = 1$$$, тогда произведение: $$$a_{6} \cdot a_{9} = 2$$$ является простым числом.
В четвертом тестовом примере не существует подходящих пар.
В пятом тестовом примере подходят пять пар:
- $$$i = 1, k = 1$$$, тогда произведение: $$$a_{1} \cdot a_{2} = 2$$$ является простым числом.
- $$$i = 1, k = 2$$$, тогда произведение: $$$a_{1} \cdot a_{2} \cdot a_{3} = 2$$$ является простым числом.
- $$$i = 1, k = 3$$$, тогда произведение: $$$a_{1} \cdot a_{2} \cdot a_{3} \cdot a_{4} = 2$$$ является простым числом.
- $$$i = 2, k = 1$$$, тогда произведение: $$$a_{2} \cdot a_{3} = 2$$$ является простым числом.
- $$$i = 2, k = 2$$$, тогда произведение: $$$a_{2} \cdot a_{3} \cdot a_{4} = 2$$$ является простым числом.
В шестом тестовом примере не существует подходящих пар.
