该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

得益于你的帮助，lfq美美得吃，现在lfq的仓库里有n个种类的大红，具体来说，对于从 1 到 n 的每一个 i，lfq拥有 $a_i$ 个该种类的大红，例如，当i=1时，$a_1$=20，代表此时，lfq拥有第一种大红的数量为20，当i=2时，$a_2$=60,代表此时，lfq拥有第二种大红的数量为60。

此外，交易行提供每种类型的大红（不限数量）。lfq拥有 k 枚哈夫币，因此lfq最多可以从交易行购买 k 个新的大红，并且lfq购买的大红可以包含 1 到 n之间的任意整数，换句话说，lfq可以用这k枚哈夫币购买任意种类的大红。

lfq正在为自己摸到如此多的大红而感到高兴时，可恶的cl又来欺负lfq了，cl要求lfq必须将所有大红按照以下规则进行分组：

• 所有分组必须具有相同的大小，即每一组中大红的数量；
• 同一分组内不得有相同种类的大红。

cl还要求lfq在找出进行最优分配后，告诉他分组可能的最大尺寸。
如果lfq不这样做或者回答错误，cl就要使用他的power来欺负lfq，请你再次帮帮可怜的lfq
注意：你可以不购买大红，你可以把大红可以理解为商品，而你可以选择是否购买大红

​输入​

每个测试包含多个测试用例。第一行包含测试用例的数量 t (1 ≤ t ≤ 10⁴)。随后是测试用例的描述。

每个测试用例的第一行包含两个整数 n, k (1 ≤ n ≤ 2 × 10⁵, 0 ≤ k ≤ 10¹⁶) —— 分别是不同大红类型的数量以及哈夫币的数量。

每个测试用例的第二行包含 n 个整数 a₁, a₂, ..., aₙ (0 ≤ aᵢ ≤ 10¹⁰, Σ aᵢ ≥ 1) —— 表示初始时你拥有的每种类型 i (1 ≤ i ≤ n) 的大红数量。

保证所有测试用例的 n 的总和不超过 2 × 10⁵。

​输出​

对于每个测试用例，输出一个整数：表示在最优操作下，分组可能的最大尺寸。

Samples

9
3 1
3 2 2
5 4
2 6 1 2 4
2 100
1410065408 10000000000
10 8
7 4 6 6 9 3 10 2 8 7
2 12
2 2
2 70
0 1
1 0
1
3 0
2 1 2
3 1
0 3 3

2
3
1
7
2
2
1
1
2

注意​

在第一个测试用例中，lfq可以购买一个种类为 1 的大红，这样lfq的大红就变成了 [1,1,1,1,2,2,3,3]。你可以将它们分成以下几组：[1,2],[1,2],[1,3],[1,3]。这些分组的大小都是 2，并且每个分组内的大红种类都是不同的。可以证明，lfq无法得到分组大小大于 2 的划分方案，因此答案是 2。

在第二个测试用例中，lfq可以购买两个种类为 1 的大红和一个种类为 3 的大红，这样lfq的大红就变成了 [1,1,1,1,2,2,2,2,2,2,3,3,4,4,5,5,5,5]。这些大红可以被划分为 [1,2,3],[1,2,4],[1,2,5],[1,2,5],[2,3,5],[2,4,5]。可以证明，lfq无法得分组大小大于 3 的划分方案，因此答案是 3。

Limitation

1s, 1024KiB for each test case.