CF1873F.Money Trees

Luca is in front of a row of $n$ trees. The $i$-th tree has $a_i$ fruit and height $h_i$.

He wants to choose a contiguous subarray of the array $[h_l, h_{l+1}, \dots, h_r]$ such that for each $i$ ($l \leq i \lt r$), $h_i$ is divisible$^{\dagger}$ by $h_{i+1}$. He will collect all the fruit from each of the trees in the subarray (that is, he will collect $a_l + a_{l+1} + \dots + a_r$ fruits). However, if he collects more than $k$ fruits in total, he will get caught.

What is the maximum length of a subarray Luca can choose so he doesn't get caught?

$^{\dagger}$ $x$ is divisible by $y$ if the ratio $\frac{x}{y}$ is an integer.

卢卡站在一排 $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$ 整除。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first of each test case line contains two space-separated integers $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq k \leq 10^9$) — the number of trees and the maximum amount of fruits Luca can collect without getting caught.

The second line of each test case contains $n$ space-separated integers $a_i$ ($1 \leq a_i \leq 10^4$) — the number of fruits in the $i$-th tree.

The third line of each test case contains $n$ space-separated integers $h_i$ ($1 \leq h_i \leq 10^9$) — the height of the $i$-th tree.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例的第一行包含两个以空格分隔的整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq k \leq 10^9$），分别表示树的数量以及Luca在不被发现的前提下最多能采集的水果总数。

每个测试用例的第二行包含 $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$。

For each test case output a single integer, the length of the maximum length contiguous subarray satisfying the conditions, or $0$ if there is no such subarray.

对于每个测试用例，输出一个整数：满足条件的最长连续子数组的长度；若不存在这样的子数组，则输出 $0$。

In the first test case, Luca can select the subarray with $l=1$ and $r=3$.

In the second test case, Luca can select the subarray with $l=3$ and $r=4$.

In the third test case, Luca can select the subarray with $l=2$ and $r=2$.

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

在第二个测试用例中，Luca 可以选择满足 $l=3$ 和 $r=4$ 的子数组。

在第三个测试用例中，Luca 可以选择满足 $l=2$ 和 $r=2$ 的子数组。