你有一个圆形的轮子。它外周的周长为 $k$ 米。

你在平整的表面上画了一条很长的直线，并将轮子放在上面，然后执行了 $n$ 次以下操作：沿直线滚动轮子，交替改变方向。也就是说，如果在第 $i$ 次操作中轮子向前滚动，那么在第 $i+1$ 次操作中它会向后滚动，反之亦然。在第 $i$ 次操作中，轮子恰好滚动了 $a_i$ 米。

现在，你想知道轮子外周上的任意点接触地面的最少次数和最多次数。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。

接下来是 $t$ 组测试用例的描述。每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 3 \cdot 10^5$，$1 \le k \le 10^{18}$)，分别表示操作次数和轮子的周长。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$)，表示轮子在第 $1, 2, \dots, n$ 次操作中滚动的距离。

保证所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

输出格式

对于每个测试用例，输出两个整数：轮子外周上的任意点接触地面的最少次数和最多次数。

样例

输入样例 1

2
3 4
4 8 4
2 7
6 5

输出样例 1

4 5
0 2

说明

请注意，在本题中，输入和输出数据可能非常大。建议使用您所用编程语言中可用的快速输入输出方法。