A. Инкрементальный подмассив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Schtiffles - Marbl
⠀

Джеймс учит числа, и ему нравится писать их на огромной доске, слева направо.

  • Сначала Джеймс пишет число $$$1$$$.
  • Затем Джеймс снова пишет $$$1$$$, а потом $$$2$$$.
  • Затем Джеймс пишет $$$1$$$, $$$2$$$, $$$3$$$.
  • $$$\ldots$$$
  • В конце Джеймс пишет $$$1$$$, $$$2$$$, $$$3$$$, $$$\ldots$$$, $$$n$$$.

Например, для $$$n = 5$$$ числа, написанные Джеймсом, образуют массив $$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$$.

У Джеймса есть список любимых чисел $$$a_1, a_2, \ldots, a_m$$$, и он хочет подсчитать, сколько подмассивов массива $$$b$$$ равны $$$a_1, a_2, \ldots, a_m$$$. $$$^{\text{∗}}$$$

Джеймс уже уверен, что $$$a_1, a_2, \ldots, a_m$$$ является подмассивом массива $$$b$$$, так что ответ будет как минимум $$$1$$$.

$$$^{\text{∗}}$$$Подмассивы массива $$$[v_1, v_2, \ldots, v_k]$$$ генерируются следующим образом: для каждых $$$l, r$$$, таких что $$$1 \leq l \leq r \leq k$$$, массив $$$[v_l, v_{l+1}, \ldots, v_r]$$$ является подмассивом. Таким образом, всего существует $$$k(k+1)/2$$$ подмассивов, и некоторые из них могут быть равны.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 200$$$) — максимальное число, написанное Джеймсом, и длину массива $$$a_1, a_2, \ldots, a_m$$$.

Вторая строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \leq a_i \leq 10^5$$$) — любимые числа Джеймса.

Гарантируется, что входные данные таковы, что ответ всегда будет как минимум $$$1$$$.

Обратите внимание, что нет ограничений на сумму $$$n$$$ и $$$m$$$ по всем наборам входных данных.

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

Для каждого набора входных данных выведите одну строку, содержащую целое число: количество подмассивов массива $$$b$$$, которые равны $$$a_1, a_2, \ldots, a_m$$$.

Пример
Входные данные
5
4 1
1
5 3
1 2 3
6 6
3 1 2 3 4 1
100000 1
100000
4 2
1 1
Выходные данные
4
3
1
1
1
Примечание

В первом наборе входных данных на доске записаны числа

$$$$$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]$$$$$$

и у Джеймса только одно любимое число: число $$$1$$$. Существует $$$4$$$ подмассива массива $$$b$$$, равных $$$[1]$$$ (выделены красным):

  • $$$[\color{red}{1}, 1, 2, 1, 2, 3, 1, 2, 3, 4]$$$;
  • $$$[1, \color{red}{1}, 2, 1, 2, 3, 1, 2, 3, 4]$$$;
  • $$$[1, 1, 2, \color{red}{1}, 2, 3, 1, 2, 3, 4]$$$;
  • $$$[1, 1, 2, 1, 2, 3, \color{red}{1}, 2, 3, 4]$$$.

Во втором наборе входных данных на доске записаны числа

$$$$$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$$$$$

и список любимых чисел Джеймса равен $$$[1, 2, 3]$$$. Существует $$$3$$$ подмассива массива $$$b$$$, равных $$$[1, 2, 3]$$$ (выделены красным):

  • $$$[1, 1, 2, \color{red}{1, 2, 3}, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$$;
  • $$$[1, 1, 2, 1, 2, 3, \color{red}{1, 2, 3}, 4, 1, 2, 3, 4, 5]$$$;
  • $$$[1, 1, 2, 1, 2, 3, 1, 2, 3, 4, \color{red}{1, 2, 3}, 4, 5]$$$.

В третьем наборе входных данных на доске записаны числа

$$$$$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$$$$$$

и список любимых чисел Джеймса равен $$$[3, 1, 2, 3, 4, 1]$$$. Существует только $$$1$$$ подмассив массива $$$b$$$, равный $$$[3, 1, 2, 3, 4, 1]$$$ (выделен красным):

  • $$$[1, 1, 2, 1, 2, \color{red}{3, 1, 2, 3, 4, 1}, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$$$.