我赌你不会做

时间限制：2s

空间限制：256MB

题目描述

黑板上有 $n$ 个整数 $a_1,a_2,\cdots,a_n$。给定参数 $k$，你可以进行以下操作任意（可以为 $0$）次：

• 选择一个黑板上的数 $x$；
• 擦去 $x$；
• 写下两个整数 $y,z$，要求满足 $x+k=y+z$。

请问经过若干次操作后，能否使得所有的数都相同。如果能，求出最少的操作次数。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示数据组数。

每组数据包含两行：

• 第一行两个整数 $n$ 和 $k$，其意义参考题目描述。
• 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

对于每组数据，输出一行一个整数，表示最少的操作次数。如果不存在，输出 $-1$。

样例 #1

样例输入 #1

9
2 1
3 4
2 3
7 11
3 10
100 40 100
2 1
1 2
2 2
1 2
1 327869541
327869541
5 26250314066
439986238782 581370817372 409476934981 287439719777 737637983182
5 616753575719
321037808624 222034505841 214063039282 441536506916 464097941819
5 431813672576
393004301966 405902283416 900951084746 672201172466 518769038906

样例输出 #1

3
1
4
-1
-1
0
3119
28999960732
-1

数据范围

对于所有数据，满足 $1 \le \sum n \le 2 \cdot 10^5$，$1 \leq k \leq 10^{12}$，$1 \le a_i \le 10^{12}$。

提示

对于第一组数据，$k=1$。你可以通过如下操作使得所有数都等于 $2$：

• 擦去 $x=4$，写下 $(y,z)=(2,3)$。现在黑板上有 $\{3,2,3\}$。
• 擦去 $x=3$，写下 $(y,z)=(2,2)$。现在黑板上有 $\{2,2,2,3\}$​。
• 擦去 $x=3$，写下 $(y,z)=(2,2)$。现在黑板上有 $\{2,2,2,2,2\}$。

操作次数为 $3$​。可以证明不存在次数更少的操作方案。

对于第二组数据，$k=3$。你可以通过如下操作使得所有数都等于 $7$：

• 擦去 $x=11$，写下 $(y,z)=(7,7)$。现在黑板上有 $\{7,7,7\}$​。

对于第三组数据，$k=10$。你可以通过如下操作使得所有数都等于 $40$：

• 擦去 $x=100$，写下 $(y,z)=(70,40)$。现在黑板上有 $\{70,40,40,100\}$。
• 擦去 $x=70$，写下 $(y,z)=(40,40)$。现在黑板上有 $\{40,40,40,40,100\}$​。
• 擦去 $x=100$，写下 $(y,z)=(70,40)$。现在黑板上有 $\{40,40,40,40,40,70\}$。
• 擦去 $x=70$，写下 $(y,z)=(40,40)$。现在黑板上有 $\{40,40,40,40,40,40,40\}$​​。

对于第四组数据，不存在合法的操作方案。