给定一个由非负整数组成的非递减数组 $$$a_1, a_2, \ldots, a_n$$$。此外,您还会获得一个正整数 $$$k$$$。
您想要找到 $$$m$$$ 非负整数的非递减数组 $$$b_1, b_2, \ldots, b_m$$$,这样:
- 对于所有 $$$1 \leq i \leq m$$$,$$$b_i$$$ 的大小等于 $$$n$$$。
- 对于所有 $$$1 \leq j \leq n$$$,$$$a_j = b_{1, j} + b_{2, j} + \ldots + b_{m, j}$$$。换句话说,数组 $$$a$$$ 是数组 $$$b_i$$$ 的和。
- 对于所有 $$$1 \leq i \leq m$$$,数组 $$$b_i$$$ 中不同元素的数量最多为 $$$k$$$。
求 $$$m$$$ 的最小可能值,或者报告不存在可能的 $$$m$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$):测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq k \leq n$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 100$$$, $$$a_n > 0$$$)。
输出
对于每个测试用例,打印一个整数:$$$m$$$ 的最小可能值。如果没有这样的$$$m$$$,则打印$$$-1$$$。
示例
输入 #1
6 4 1 0 0 0 1 3 1 3 3 3 11 3 0 1 2 2 3 3 3 4 4 4 4 5 3 1 2 3 4 5 9 4 2 2 3 5 7 11 13 13 17 10 7 0 1 1 2 3 3 4 5 5 6
输出 #1
-1 1 2 2 2 1
注意
在第一个测试用例中,不可能有$$$m$$$,因为所有数组的所有元素都应该等于$$$0$$$。但在这种情况下,不可能得到 $$$a_4 = 1$$$ 作为零的总和。
在第二个测试用例中,我们可以取 $$$b_1 = [3, 3, 3]$$$。 $$$1$$$ 是 $$$m$$$ 的最小可能值。
在第三个测试用例中,我们可以取 $$$b_1 = [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]$$$ 和 $$$b_2 = [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2]$$$。很容易看出,对于所有$$$i$$$,$$$a_i = b_{1, i} + b_{2, i}$$$,并且$$$b_1$$$和$$$b_2$$$中不同元素的数量等于$$$3$$$(因此最多为$$$3$$$)。可以证明$$$2$$$是$$$m$$$的最小可能值。