310915: CF1909D. Split Plus K

D. Split Plus Ktime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputeliteLAQ - Desert Ruins⠀

There are $n$ positive integers $a_1, a_2, \dots, a_n$ on a blackboard. You are also given a positive integer $k$. You can perform the following operation some (possibly $0$) times:

• choose a number $x$ on the blackboard;
• erase one occurrence of $x$;
• write two positive integers $y$, $z$ such that $y+z = x+k$ on the blackboard.

Is it possible to make all the numbers on the blackboard equal? If yes, what is the minimum number of operations you need?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $1 \leq k \leq 10^{12}$) — the number of integers initially on the blackboard and the constant $k$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{12}$) — the initial state of the blackboard.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single line containing an integer: the minimum number of operations you need to make all the numbers on the blackboard equal, or $-1$ if it is impossible.

ExampleInput

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

Output

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

Note

In the first test case, $k = 1$. You can make all the numbers on the blackboard equal to $2$ with the following operations:

• Erase $x = 4$ and write $(y, z) = (2, 3)$. Note that $y+z=x+k$. The blackboard now contains the multiset $\{3, 2, 3\}$.
• Erase $x = 3$ and write $(y, z) = (2, 2)$. Note that $y+z=x+k$. The blackboard now contains $\{2, 2, 2, 3\}$.
• Erase $x = 3$ and write $(y, z) = (2, 2)$. Note that $y+z=x+k$. The blackboard now contains $\{2, 2, 2, 2, 2\}$.

This makes all the numbers equal in $3$ operations. It can be shown that you cannot make all the numbers equal in less than $3$ operations.

In the second test case, $k = 3$. You can make all the numbers on the blackboard equal to $7$ with the following operation:

• Erase $x = 11$ and write $(y, z) = (7, 7)$. Note that $y+z=x+k$. The blackboard now contains $\{7, 7, 7\}$.

In the third test case, $k = 10$. You can make all the numbers on the blackboard equal to $40$ with the following operations:

• Erase $x = 100$ and write $(y, z) = (70, 40)$. Note that $y+z=x+k$. The blackboard now contains $\{70, 40, 40, 100\}$.
• Erase $x = 70$ and write $(y, z) = (40, 40)$. Note that $y+z=x+k$. The blackboard now contains $\{40, 40, 40, 40, 100\}$.
• Erase $x = 100$ and write $(y, z) = (40, 70)$. Note that $y+z=x+k$. The blackboard now contains $\{40, 40, 40, 40, 40, 70\}$.
• Erase $x = 70$ and write $(y, z) = (40, 40)$. Note that $y+z=x+k$. The blackboard now contains $\{40, 40, 40, 40, 40, 40, 40\}$.

In the fourth and in the fifth test case, you can show that it is impossible to make all the numbers on the blackboard equal.

题目大意：给定一个黑板上的一系列正整数 $ a_1, a_2, \dots, a_n $ 和一个正整数 $ k $。你可以执行以下操作若干次（可能为0次）：

1. 在黑板上选择一个数 $ x $；
2. 擦除一个 $ x $；
3. 在黑板上写下两个正整数 $ y $ 和 $ z $，使得 $ y + z = x + k $。

问是否可能使黑板上所有的数相等？如果可能，需要执行的最小操作次数是多少？

输入输出数据格式：

输入：
- 第一行包含一个整数 $ t $，表示测试用例的数量，$ 1 \le t \le 10^4 $；
- 每个测试用例包含三行：
- 第一行包含两个整数 $ n $ 和 $ k $，$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \leq k \leq 10^{12} $，分别表示黑板上整数的数量和常数 $ k $；
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $，$ 1 \le a_i \le 10^{12} $，表示黑板的初始状态；
- 所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。

输出：
- 对于每个测试用例，输出一行，包含一个整数：使黑板上所有数相等所需的最小操作次数，或者如果不可能，输出 -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
```

输出：
```
3
1
4
-1
-1
0
3119
28999960732
-1
```题目大意：给定一个黑板上的一系列正整数 $ a_1, a_2, \dots, a_n $ 和一个正整数 $ k $。你可以执行以下操作若干次（可能为0次）： 1. 在黑板上选择一个数 $ x $； 2. 擦除一个 $ x $； 3. 在黑板上写下两个正整数 $ y $ 和 $ z $，使得 $ y + z = x + k $。 问是否可能使黑板上所有的数相等？如果可能，需要执行的最小操作次数是多少？ 输入输出数据格式： 输入： - 第一行包含一个整数 $ t $，表示测试用例的数量，$ 1 \le t \le 10^4 $； - 每个测试用例包含三行： - 第一行包含两个整数 $ n $ 和 $ k $，$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \leq k \leq 10^{12} $，分别表示黑板上整数的数量和常数 $ k $； - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $，$ 1 \le a_i \le 10^{12} $，表示黑板的初始状态； - 所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 输出： - 对于每个测试用例，输出一行，包含一个整数：使黑板上所有数相等所需的最小操作次数，或者如果不可能，输出 -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 ``` 输出： ``` 3 1 4 -1 -1 0 3119 28999960732 -1 ```