Chiaki is going to create n sets S₀,S₁,...,S_n-1 under the following restrictions:

•  |S_i| = m.
• .
•   should be minimized.

Note that |S| means the size of set S and means set difference which is defined as

输入描述:

There are multiple test cases. The first line of the input contains an integer T, indicating the number of
test cases. For each test case:
The first line contains two integers n and m (2 ≤ n ≤ 106, 0 ≤ m ≤ 1018) -- the number of sets and the size of each set.
The second line contains n integers l0,l1,...,ln-1 (0 ≤ li ≤ 1018).
It's guaranteed that the sum of n in all test cases will not exceed 106.

输出描述:

For each test case, output an integer denoting the minimum value of . Or -1 if the restrictions cannot be satisfied.

2
3 1
1 1 1
3 2
1 1 1

3
3