在小王面前有 $n$ 棵树，第 $i$ 棵树的高度为 $h_i$，上面有 $a_i$ 个果子。

他可以选择数组中的任意一段连续子区间 $[l,r]$，使得对于该区间里的每个 $i(l\le i<r)$，都满足 $h_i\mod h_{i+1}==0$，若能满足这个条件，小王就可以把这个区间里的所有果子都拿走，即他会拿走 $a_l +a_{l+1}+....+a_r$个果子。

但是，这些果树并不属于他，如果他拿走了超过 $k$ 个果子，他就会被生气的农场主抓住，并被农场主狠狠地教训。

现在请问，小王可以选择的连续子区间的最大长度是多少？of course，小王当然是不想被农场主抓住的，所以请你帮帮他吧！

输入描述

第一行输入一个正整数 $t$，表示有 $t$ 组测试用例。

接下来输入 $t$ 组测试用例，对于每组测试用例：

第一行输入两个正整数 $n$ 和 $k$，表示树的数量和最多能拿走多少个果子。

第二行输入 $n$ 个正整数 $a_i$，表示每棵树上果子的数量。

第三行输入 $n$ 个正整数 $h_i$，表示每棵树的高度。

【数据范围】 对于 $15\%$ 的数据，保证所有 $n$ 的总和不超过 $10^3$。

对于全部的测试点，保证 $1\le t\le 1000,1\le n\le 10^6,1\le k\le 10^9,1\le a_i\le 10^4,1\le h_i\le 10^9$。

保证所有测试点中，测试样例里所有 $n$ 的总和不超过 $10^6$。

输出描述

对于每组测试用例，输出能选取的连续子区间的最大长度是多少，如果没有任何一个区间可以选取，输出 $0$。

用例输入 1

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

用例输出 1

3
2
1
0
3

提示

【样例 1 说明】 对于第一组测试用例，可以选择区间 $[1,3]$。

对于第二组测试用例，可以选择区间 $[3,4]$。

对于第三组测试用例，可以选择区间 $[2,2]$。