题目描述

给你一个整数数组 $a_1, a_2, \ldots, a_n$ 和一个整数 $k$ 。您需要用最少的运算使数组漂亮。

在进行操作前，可以随意对数组元素进行洗牌。对于一个操作，您可以执行以下操作：

• 选择一个索引 $1 \leq i \leq n$ 、
• 生成 $a_i = a_i + k$ 。

如果所有的 $1 \leq i \leq n$ 都是 $b_i = b_{n - i + 1}$ ，那么数组 $b_1, b_2, \ldots, b_n$ 就是优美的。

求使数组美丽所需的最小运算次数，或报告不可能。

输入格式

每个测试由多组输入数据组成。第一行包含一个整数 $t$ ( $1 \leq t \leq 10^4$ ) - 输入数据集的数量。然后是它们的说明。

每组输入数据的第一行包含两个整数 $n$ 和 $k$ ( $1 \leq n \leq 10^5$ , $1 \leq k \leq 10^9$ )--数组的大小 $a$ 和问题陈述中的数字 $k$ 。

每组输入数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 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]$ ，非常漂亮。

在第八组输入数据中，没有一组运算，也无法通过洗元素来使数组变得漂亮。

在第九组输入数据中，数组已经很漂亮了。

$30 \%$的数据，$1 \le n,k,a_i\le 1000$

$70 \%$的数据，$1 \le n,k,a_i\le 10^5$

$100 \%$的数据，$1 \le n \le 10^5 ,1 \le k,a_i \le 10^9$

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