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

В очередной день Егору стало скучно, и он решил чем-нибудь заняться. Но так как у него нет друзей, он придумал игру, в которую и хочет сыграть.

У Егора есть колода из $$$n$$$ карт, на $$$i$$$-й карте сверху написано какое-то число $$$a_i$$$. Егор хочет сыграть в игру некоторое количество раундов, пока не закончатся карты. В каждом раунде он берет некоторое ненулевое количество карт с верха колоды и заканчивает раунд. Если сумма чисел на набранных за раунд картах находится между $$$l$$$ и $$$r$$$ включительно, то раунд считается выигранным, иначе проигранным.

Егор знает, в каком порядке идут числа на картах в колоде. Помогите Егору узнать, какое наибольшее количество раундов он сможет выиграть в такой игре. Обратите внимание, что Егор не обязан выигрывать раунды подряд.

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

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

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$1 \le n \le 10^{5}$$$, $$$1 \le l \le r \le 10^9$$$).

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

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

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

Для каждого набора входных данных выведите одно число — наибольшее количество раундов, которое сможет выиграть Егор.

Пример
Входные данные
8
5 3 10
2 1 11 3 7
10 1 5
17 8 12 11 7 11 21 13 10 8
3 4 5
3 4 2
8 12 25
10 7 5 13 8 9 12 7
2 3 3
5 2
9 7 9
2 10 5 1 3 7 6 2 3
1 8 10
9
5 5 6
1 4 2 6 4
Выходные данные
3
0
1
4
0
3
1
2
Примечание

В первом наборе входных данных Егор может выиграть $$$3$$$ раунда:

  • В первом раунде взять $$$2$$$ верхние карты со значениями $$$2$$$ и $$$1$$$ и выиграть, так как в сумме они дают $$$3$$$. Колода после этого будет выглядеть так: $$$[11, 3, 7]$$$.
  • Во втором раунде взять верхнюю карту и проиграть, так как ее значение $$$11$$$ больше $$$r = 10$$$. Колода после этого будет выглядеть так: $$$[3, 7]$$$.
  • В третьем раунде взять верхнюю карту со значением $$$3$$$ и выиграть. Колода после этого будет выглядеть так: $$$[7]$$$.
  • После этого в четвертом раунде Егору остается только взять последнюю карту в колоде со значением $$$7$$$ и снова выиграть.

Во втором наборе входных данных Егор не сможет выиграть ни одного раунда, как бы он не старался.

В третьем наборе входных данных можно каждый раунд брать по одной карте, тогда первый и третий раунд будут проигрышными, а второй — выигрышным.

В четвертом наборе данных можно брать по две карты каждый раунд и всегда выигрывать.