题目描述

作为一只生活在魔法森林的小刺猬 Dash，他需要在大寒来临之前储备好自己最爱的魔法浆果。

Dash 在洞穴中已经储存了 $n$ 种魔法浆果，编号为 $1 \sim n$。他对浆果的喜好程度从 $1$ 号浆果到 $n$ 号浆果依次递减。对于第 $i$ 种浆果，他目前储存了 $a_i$ 份。当 Dash 更喜欢的某种浆果的数量严格多于某种不那么喜欢的浆果时，他会获得 $1$ 点快乐值。

然而，Dash 对现有的储备并不满意。他计划外出觅食 $x$ 次，每次觅食都能获得每种浆果各 $1$ 份。但是由于洞穴空间限制，当任何一种浆果的数量达到 $m$ 时，Dash 必须吃掉 $m$ 份这种浆果以腾出空间。

Dash 想要最大化他的快乐值，你能帮他计算出最大快乐值以及实现这一目标所需的最小觅食次数吗？

输入格式

第一行是测试组数 $T(1\le T\le 10^3)$。

对于每组测试数据：

第一行包含两个整数 $n(1\le n\le 3\times 10^5)$ 和 $m(1\le m\le 10^9)$，表示浆果的种类数和每种浆果的最大数量。

第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n (0 \le a_i < m)$，分别表示第 $i$ 种浆果目前的数量。

保证所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行包含两个整数 $h$ 和 $x$，分别表示 Dash 可以获得的最大快乐值和实现这一目标所需的最小觅食次数。

如果存在多个 $x$ 使得 $h$ 最大化，输出最小的 $x$。

样例

2
5 10
3 7 2 3 0
5 10
7 8 9 6 9

7 0
7 1

数据范围

对于所有测试点，均有$1\le T\le 10^3,1\le \sum n\le 10^6,1\le m\le 10^9,0\le a_i<m$。