题目描述

夏目章人（Natsume Akito）刚刚在一个新世界苏醒，便立即收到了他的第一个任务！系统为他提供了一个包含 $n$ 个零的数组 $a$，以及两个整数 $k$ 和 $p$。

在每次操作中，章人需要选择两个整数 $i$ 和 $x$（满足 $1 \le i \le n$ 且 $-p \le x \le p$），然后执行赋值操作 $a_i = x$。

章人仍未完全适应如何控制他的新身体，因此请你帮他计算使数组所有元素之和等于 $k$ 所需的最少操作次数，或者告诉他这是不可能的。

输入格式

第一行输入包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的唯一一行包含三个整数 $n$, $k$, $p$（$1 \le n \le 50$，$-2500 \le k \le 2500$，$1 \le p \le 50$）—— 分别表示数组长度、目标总和以及可替换数值的范围边界。

输出格式

对于每个测试用例，输出使数组最终总和为 $k$ 所需的最少操作次数；若无法达成，则输出 $-1$。

说明/提示

第五个样例中，数组初始总和为零，因此无需任何操作。

第六个样例中，数组能达到的最大总和为 $9$（将唯一元素赋值为 $9$），因此无法通过任何操作得到总和 $10$。

第七个样例中，仅需一次操作 $a_3 = -7$ 即可达成目标。

翻译由 DeepSeek R1 完成

样例

8
21 100 10
9 -420 42
5 -7 2
13 37 7
10 0 49
1 10 9
7 -7 7
20 31 1

10
-1
4
6
0
-1
1
-1