Lzw 正在上运筹学课。今天老师讲的是装箱问题以及一些求解该问题的近似算法。

在装箱问题中，必须将不同体积的物品装入固定容量为 $C$ 的有限个箱子中，以使所使用的箱子数量最少。在计算复杂性理论中，这是一个组合 NP-hard 问题。

这里有两种经典的近似算法：

• 首次适应算法 (First Fit Algorithm)：按输入顺序考虑物品，并维护一个初始为空的箱子列表。在每一步中，它尝试将当前物品放入列表中第一个能容纳该物品的箱子中。如果没有找到合适的箱子，它会在列表末尾添加一个新箱子，并将物品放入该新箱子中。
• 最佳适应算法 (Best Fit Algorithm)：按输入顺序考虑物品，并维护一个初始为空的箱子列表。在每一步中，它尝试将当前物品放入能容纳该物品的最佳箱子中。“最佳”意味着如果有多个箱子可以容纳该物品，则选择剩余空间最小的那个箱子。如果没有找到合适的箱子，则添加一个新箱子，并将物品放入该新箱子中。

请帮助 Lzw 实现这两种算法，并找出每种算法分别会使用多少个箱子。

输入格式

输入包含多个测试用例。输入的第一行包含一个正整数 $T$，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, C$ ($1 \le n \le 10^6, 1 \le C \le 10^9$)，分别表示物品数量和每个箱子的容量。第二行包含 $n$ 个整数，其中第 $i$ 个 ($1 \le i \le n$) 整数 $a_i$ ($1 \le a_i \le C$) 表示第 $i$ 个物品的体积。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，打印一行，包含两个整数，分别表示首次适应算法和最佳适应算法所使用的箱子数量。

样例

输入 1

2
2 2
1 1
5 10
5 8 2 5 9

输出 1

1 1
4 3