E. 美丽数组

• 时间限制：每个测试点 $2$ 秒
• 内存限制：每个测试点 $256$ 兆字节

给你一个整数数组 $a_1, a_2, \dots, a_n$ 和一个整数 $k$。你需要用最少的操作次数使其变得美丽。

在执行操作之前，你可以任意重新排列数组元素。一次操作如下：

• 选择一个下标 $1 \le i \le n$，
• 令 $a_i = a_i + k$。

如果对于所有 $1 \le i \le n$ 都有 $b_i = b_{n-i+1}$，则称数组 $b_1, b_2, \dots, b_n$ 是美丽的。

求使数组变得美丽所需的最少操作次数，如果不可能则输出 $-1$。

输入

每个测试包含若干组输入数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——输入数据的组数。接下来是每组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$1 \le k \le 10^9$）——数组 $a$ 的大小和题目中的 $k$。

每组数据的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）——数组 $a$ 的元素。

保证所有输入数据组的 $n$ 之和不超过 $2 \cdot 10^5$。

输出

对于每组输入数据，输出使数组变得美丽所需的最少操作次数，如果不可能则输出 $-1$。

示例

输入

11
1 1000000000
1
2 1
624323799 708290323
3 1
3 2 1
4 1
7 1 5 3
5 1
11 2 15 7 10
7 1
1 8 2 16 8 16 31
13 1
2 1 1 3 3 11 12 22 45 777 777 1500 74
10 2
1 2 1 2 1 2 1 2 1 2
11 2
1 2 1 2 1 2 1 2 1 2 1
13 3
2 3 9 14 17 10 22 20 18 30 1 4 28
5 1
2 3 5 3 5

输出

0
83966524
1
4
6
1
48
-1
0
14
0

注

• 在第一组数据中，数组已经美丽。
• 在第二组数据中，你可以在操作前重新排列数组，然后对下标 $i=1$ 执行 $83966524$ 次操作。
• 在第三组数据中，你可以将数组 $a$ 重排为 $[2,3,1]$，然后对 $i=3$ 执行一次操作得到 $[2,3,2]$，该数组美丽。
• 在第八组数据中，无论如何操作和重排都无法使数组变得美丽。
• 在第九组数据中，数组已经美丽。