夏目秋人刚刚在新世界醒来,立刻就接到了第一个任务!系统为他提供了一个由$$$n$$$个零组成的数组$$$a$$$、一个整数$$$k$$$和一个整数$$$p$$$。
在一次操作中,Akito 选择两个整数 $$$i$$$ 和 $$$x$$$,使得 $$$1 \le i \le n$$$ 和 $$$-p \le x \le p$$$,并执行赋值 $$$a_i = x$$$。
Akito还没有完全习惯控制他的新身体,所以帮他计算一下使数组中所有元素的总和等于$$$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$$$ 的最小操作数,如果无法实现总和 $$$k$$$,则输出 $$$-1$$$。
示例
输入复制
821 100 109 -420 425 -7 213 37 710 0 491 10 97 -7 720 31 1
输出复制
10 -1 4 6 0 -1 1 -1
注意
在第五个示例中,数组的和最初为零,因此不需要任何操作。
在第六个示例中,我们可以实现的数组中的最大和为$$$9$$$(通过将数字$$$9$$$分配给单个元素),因此无法通过任何操作获得和$$$10$$$。
在第七个示例中,仅需要一次操作$$$a_3 = -7$$$。