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

Лука стоит перед рядом из $$$n$$$ деревьев. У $$$i$$$-го дерева есть $$$a_i$$$ фруктов и высота $$$h_i$$$.

Он хочет выбрать непрерывный подмассив массива $$$[h_l, h_{l+1}, \dots, h_r]$$$, такой что для каждого $$$i$$$ ($$$l \leq i < r$$$), $$$h_i$$$ делится$$$^{\dagger}$$$ на $$$h_{i+1}$$$. Он соберет все фрукты с каждого дерева в подмассиве (то есть, он соберет $$$a_l + a_{l+1} + \dots + a_r$$$ фруктов). Однако, если он соберет больше $$$k$$$ фруктов в общей сложности, его поймают.

Какова максимальная длина подмассива, который Лука может выбрать, чтобы не попасться?

$$$^{\dagger}$$$ $$$x$$$ делится на $$$y$$$, если отношение $$$\frac{x}{y}$$$ является целым числом.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа, разделенных пробелом: $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$; $$$1 \leq k \leq 10^9$$$) — количество деревьев и максимальное количество фруктов, которое Лука может собрать, не попавшись.

Вторая строка каждого набора содержит $$$n$$$ целых чисел, разделенных пробелом: $$$a_i$$$ ($$$1 \leq a_i \leq 10^4$$$) — количество фруктов в $$$i$$$-м дереве.

Третья строка каждого набора содержит $$$n$$$ целых чисел, разделенных пробелом: $$$h_i$$$ ($$$1 \leq h_i \leq 10^9$$$) — высота $$$i$$$-го дерева.

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

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

Для каждого набора входных данных выведите одно целое число, длину максимального непрерывного подмассива, удовлетворяющего условиям, или $$$0$$$, если такого подмассива нет.

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

В первом примере Лука может выбрать подмассив с $$$l=1$$$ и $$$r=3$$$.

Во втором примере Лука может выбрать подмассив с $$$l=3$$$ и $$$r=4$$$.

В третьем примере Лука может выбрать подмассив с $$$l=2$$$ и $$$r=2$$$.