C. Голодные игры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ярослав играет в компьютерную игру, и на одном из уровней перед ним оказалось $$$n$$$ выстроенных в ряд грибов. Каждый гриб имеет свой уровень ядовитости, $$$i$$$-й с начала гриб имеет уровень ядовитости $$$a_i$$$. Ярослав может выбрать два целых числа $$$1 \le l \le r \le n$$$, а затем его персонаж будет по очереди слева направо поедать грибы из этого подотрезка, то есть грибы с номерами $$$l, l+1, l+2, \ldots, r$$$.

У персонажа есть уровень отравленности $$$g$$$, изначально равный $$$0$$$. Компьютерная игра определяется числом $$$x$$$ — максимальным уровнем отравленности в любой момент времени. При поедании гриба с ядовитостью $$$k$$$ происходит следующее:

  1. К отравленности персонажа добавляется $$$k$$$.
  2. Если $$$g \leq x$$$, процесс продолжается, иначе $$$g$$$ становится равным нулю и процесс продолжается.

Ярославу стало интересно, сколько существует способов выбрать значения $$$l$$$ и $$$r$$$ таких, что итоговое значение $$$g$$$ не равно нулю. Помогите Ярославу найти это число!

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$x$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \le x \le 10^9$$$) — количество грибов и максимальный уровень отравленности.

Вторая строка каждого набора входных данных содержит $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

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

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

Для каждого набора входных данных выведите одно число — количество подотрезков, таких что итоговое значение $$$g$$$ будет не равно нулю.

Пример
Входные данные
5
4 2
1 1 1 1
3 2
1 2 3
1 6
10
6 3
1 2 1 4 3 8
5 999999999
999999999 999999998 1000000000 1000000000 500000000
Выходные данные
8
2
0
10
7
Примечание

В первом наборе входных данных подходят подотрезки $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$ и $$$(4, 4)$$$.

Во втором наборе входных данных ненулевое $$$g$$$ останется только на подотрезках $$$(1, 1)$$$ и $$$(2, 2)$$$.

В третьем наборе входных данных на единственном возможном подотрезке $$$g$$$ будет равно нулю.