题目描述

光头强站在 $n$ 棵树的前面。第 $i$ 棵树有 $a_i$ 个水果和高度 $h_i$。

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

光头强能够选择的最大子数组长度是多少，以便他不会被抓住？

输入格式

第一行包含一个整数 $t(1≤t≤1000)$ — 测试用例的数量。

每个测试用例的第一行包含两个以空格分隔的整数 $n$ 和 $k(1≤n≤2×10^5; 1≤k≤10^9)$ — 树的数量和光头强可以在不被抓住的情况下收集的最大水果量。

每个测试用例的第二行包含 $n$ 个以空格分隔的整数 $a_i(1≤a_i≤10^4)$ — 第 $i$ 棵树上的水果数量。

每个测试用例的第三行包含 $n$ 个以空格分隔的整数 $h_i(1≤h_i≤10^9)$ — 第 $i$ 棵树的高度。

所有测试用例中 $n$ 的总和不超过 $2×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$。