一个开明的异星种族计划同化一个恒星系，以帮助其居民实现完美。他们可能会反抗，但正如你们所知，反抗是徒劳的。

该系统中共有 $n$ 个行星，分别居住着 $a_1, a_2, \dots, a_n$ 个居民。外星人初始拥有 $k$ 艘同化飞船，并可以执行以下任意操作：

• 入侵：需要派遣一部分舰队降落到某个行星上。降落的飞船数量 $s$ 必须大于或等于该行星的人口 $m$。入侵完成后，这些飞船消失，该行星被征服，且现在拥有 $m + s$ 个居民。
• 动员：从一个已被征服的行星上，制造出数量等于该行星人口的新飞船。每个行星最多只能被动员一次。

对于外星人来说，入侵既简单又自然，但动员却有些棘手。请帮助他们以最少的动员次数征服系统中的所有行星。

输入格式

第一行包含测试用例的数量 $z$ ($1 \le z \le 30$)。接下来是各个测试用例，格式如下：

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 200\,000$; $1 \le k \le 10^9$)，分别表示行星数量和外星人初始舰队的大小。第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示各个行星的人口。

所有测试用例的 $n$ 之和不超过 $500\,000$。

输出格式

对于每个测试用例，输出一个整数：征服所有行星所需的最少动员次数。如果无法完成征服，则输出 $-1$。

样例

输入 1

4
3 15
6 5 26
3 15
6 5 27
2 1000000000
500123123 497000000
7 2
6 2 4 1 9 3 12

输出 1

2
-1
0
4