C. Подотрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел. Также у него есть любимое целое число $$$k$$$ ($$$k \lt n$$$).

Назовем последовательность подряд идущих элементов массива с индексами от $$$l$$$ до $$$r$$$ ($$$1 \le l \le r \le n$$$) подотрезком массива. Монокарп называет подотрезок массива $$$k$$$-сбалансированным, если выполняются следующие условия:

  • сумма всех элементов на подотрезке от $$$l$$$ до $$$r$$$ включительно делится на число $$$k$$$ без остатка;
  • длина этого подотрезка строго больше $$$k$$$ (то есть $$$r - l + 1 \gt k$$$).

Помогите Монокарпу определить суммарное количество $$$k$$$-сбалансированных подотрезков в массиве $$$a$$$.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \lt n \le 2 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$ и число $$$k$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Выходные данные

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

Пример
Входные данные
3
5 2
2 1 3 1 4
9 3
1 1 1 1 1 1 1 1 1
4 3
2 8 5 7
Выходные данные
2
5
0
Примечание

В первом наборе входных данных примера подходящими подотрезками являются:

  1. $$$[2, 1, 3]$$$ (сумма всех элементов $$$2 + 1 + 3 = 6$$$ делится нацело на $$$2$$$);
  2. $$$[3, 1, 4]$$$ (сумма всех элементов $$$3 + 1 + 4 = 8$$$ делится нацело на $$$2$$$).

Во втором наборе входных данных все элементы равны $$$1$$$, а $$$k = 3$$$. Подходящие подотрезки имеют длины $$$6$$$ и $$$9$$$: существует четыре подотрезка длины $$$6$$$ и один подотрезок длины $$$9$$$, поэтому ответ равен $$$5$$$.

В третьем наборе входных данных единственный подотрезок длины строго больше $$$3$$$ — весь массив. Его сумма равна $$$22$$$, что не делится на $$$3$$$, поэтому ответ равен $$$0$$$.