310704: CF1873F. Money Trees

F. Money Treestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 < 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.

Input

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$.

Output

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.

ExampleInput

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

Output

3
2
1
0
3

Note

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$.

**题目大意**：

卢卡面前有一排 $ n $ 棵树。第 $ i $ 棵树上有 $ a_i $ 个水果和高度 $ h_i $。

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

卢卡可以选择的子数组的最大长度是多少，以使他不被抓住？

**输入数据格式**：

- 第一行包含一个整数 $ 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 $。

**注意**：

- 在第一个测试用例中，卢卡可以选择 $ l=1 $ 和 $ r=3 $ 的子数组。
- 在第二个测试用例中，卢卡可以选择 $ l=3 $ 和 $ r=4 $ 的子数组。
- 在第三个测试用例中，卢卡可以选择 $ l=2 $ 和 $ r=2 $ 的子数组。**题目大意**： 卢卡面前有一排 $ n $ 棵树。第 $ i $ 棵树上有 $ a_i $ 个水果和高度 $ h_i $。 他想选择一个连续的子数组 $[h_l, h_{l+1}, \dots, h_r]$，使得对于每个 $ i $（$ l \leq i < r $），$ h_i $ 能被 $ h_{i+1} $ 整除。他将收集子数组中每棵树上的所有水果（即，他将收集 $ a_l + a_{l+1} + \dots + a_r $ 个水果）。然而，如果他总共收集超过 $ k $ 个水果，他将会被抓住。 卢卡可以选择的子数组的最大长度是多少，以使他不被抓住？ **输入数据格式**： - 第一行包含一个整数 $ 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 $。 **注意**： - 在第一个测试用例中，卢卡可以选择 $ l=1 $ 和 $ r=3 $ 的子数组。 - 在第二个测试用例中，卢卡可以选择 $ l=3 $ 和 $ r=4 $ 的子数组。 - 在第三个测试用例中，卢卡可以选择 $ l=2 $ 和 $ r=2 $ 的子数组。