A. Divan и магазин
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бизнесмен по имени Divan обожает шоколад! Сегодня он пришёл в магазин, чтобы закупиться им. Как и любой другой бизнесмен, Divan знает цену деньгам, поэтому он считает, что покупать слишком дорогие плитки шоколада не имеет никакого смысла, несмотря на всю его любовь к шоколаду. С другой же стороны, слишком дешёвый шоколад обычно слишком невкусный и вообще непонятно, зачем его покупать, ведь кроме отвращения он ничего не вызывает.

В магазине, в который он пришёл, есть $$$n$$$ различных плиток шоколада, $$$i$$$-я из которых имеет цену $$$a_i$$$ долларов. Слишком дорогой плиткой шоколада Divan считает такую, что её цена строго выше $$$r$$$ долларов. Слишком дешёвой плиткой шоколада он считает такую, что её цена строго меньше, чем $$$l$$$ долларов. Диван не будет покупать плитку, если она слишком дешёвая или слишком дорогая.

Кроме того, даже если по отдельности плитки шоколада не столь уж и дорогие, Divan, конечно, не собирается всю свою прибыль тратить на них, поэтому он ограничивает свои траты на шоколад $$$k$$$ долларами.

Ваша задача заключается в том, чтобы определить, какое максимальное число плиток шоколада Divan сможет сегодня купить.

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

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

В первой строке каждого набора заданы четыре целых числа $$$n$$$, $$$l$$$, $$$r$$$ и $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le l \le r \le 10^9$$$, $$$1 \le k \le 10^9$$$) — количество плиток в магазине, самая низкая и самая высокая цены, по которым Divan готов купить шоколадку, и бюджет, рассчитанный на покупку шоколада соответственно.

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

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

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

Пример
Входные данные
8
3 1 100 100
50 100 50
6 3 5 10
1 2 3 4 5 6
6 3 5 21
1 2 3 4 5 6
10 50 69 100
20 30 40 77 1 1 12 4 70 10000
3 50 80 30
20 60 70
10 2 7 100
2 2 2 2 2 7 7 7 7 7
4 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 1 1 1
1
Выходные данные
2
2
3
0
0
10
1
1
Примечание

В первом примере Divan сможет купить плитки шоколада под номерами $$$1$$$ и $$$3$$$ и потратит на это $$$100$$$ долларов.

Во втором примере Divan сможет купить плитки шоколада под номерами $$$3$$$ и $$$4$$$ и потратит на это $$$7$$$ долларов.

Во третьем примере Divan сможет купить плитки шоколада под номерами $$$3$$$, $$$4$$$ и $$$5$$$, потратив на это $$$12$$$ долларов.

В четвёртом примере Divan не может купить ни одной плитки шоколада, потому что каждую из них он считает либо слишком дешёвой, либо слишком дорогой.

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

В шестом примере Divan сможет купить все плитки шоколада, которые есть в магазине.