题目描述

小 z 给大家发布了一个任务！

现在他提供了一个包含 $n$ 个值均为零的数组 $a$，以及两个整数 $k$ 和 $p$。

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

小 z 请你帮他计算使数组所有元素之和等于 $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$。

4
10 0 49
1 10 9
5 7 2
5 -7 2

0
-1
4
4

说明/提示

对于样例数据中：$5,7,2$，即最初数组 $a$ 长度为 $5$：$[0,0,0,0,0]$，之后进行 $4$ 次操作；

1. 选择 $i$ 和 $x$ 分别为 $(1,2)$
2. 选择 $i$ 和 $x$ 分别为 $(2,2)$
3. 选择 $i$ 和 $x$ 分别为 $(3,2)$
4. 选择 $i$ 和 $x$ 分别为 $(4,1)$

最后 $a$ 数组为：$[2,2,2,1,0]$，数组总和为 $7$，完成任务。