题目描述

卢卡面前有一排$n$棵树。$i$棵树结了$a_i$个果，树高$h_i$。

他想从数组 $[h_l, h_{l+1}, \dots, h_r]$ 中选择一个连续的子数组，使得每一个 $i$ ($l \leq i < r$), $h_i$能被$h_{i+1}$整除$^{\dagger}$。他将收集子数组中每棵树上的所有果实（即收集$a_l + a_{l+1} + \dots + a_r$个果实）。但是，如果他收集的水果总数超过 $k$，他就会被抓。

为了不被抓到，卢卡最多可以选择多长的子数组？

$^{\dagger}$如果比值 $\frac{x}{y}$ 是整数，那么 $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$）。($1 \leq a_i \leq 10^4$) - $i$-th树中水果的数量。

每个测试用例的第三行包含 $n$ 个空格分隔的整数 $h_i$ （$1 \leq h_i \leq 10^9$）。($1 \leq h_i \leq 10^9$) - $i$（th）树的高度。

所有测试用例的$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

说明

在第一个测试案例中，Luca 可以选择带有 $l=1$ 和 $r=3$ 的子数组。

在第二个测试案例中，卢卡可以选择包含 $l=3$ 和 $r=4$ 的子数组。

在第三个测试案例中，卢卡可以选择包含 $l=2$ 和 $r=2$ 的子数组。