Want to solve the contest problems after the official contest ends? Just register for practice and you will be able to submit solutions.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Arrays Sum

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a non-decreasing array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Also you are given a positive integer $$$k$$$.

You want to find $$$m$$$ non-decreasing arrays of non-negative integers $$$b_1, b_2, \ldots, b_m$$$, such that:

- The size of $$$b_i$$$ is equal to $$$n$$$ for all $$$1 \leq i \leq m$$$.
- For all $$$1 \leq j \leq n$$$, $$$a_j = b_{1, j} + b_{2, j} + \ldots + b_{m, j}$$$. In the other word, array $$$a$$$ is the sum of arrays $$$b_i$$$.
- The number of different elements in the array $$$b_i$$$ is at most $$$k$$$ for all $$$1 \leq i \leq m$$$.

Find the minimum possible value of $$$m$$$, or report that there is no possible $$$m$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 100$$$): the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$1 \leq k \leq n$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq 100$$$, $$$a_n > 0$$$).

Output

For each test case print a single integer: the minimum possible value of $$$m$$$. If there is no such $$$m$$$, print $$$-1$$$.

Example

Input

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

Output

-1 1 2 2 2 1

Note

In the first test case, there is no possible $$$m$$$, because all elements of all arrays should be equal to $$$0$$$. But in this case, it is impossible to get $$$a_4 = 1$$$ as the sum of zeros.

In the second test case, we can take $$$b_1 = [3, 3, 3]$$$. $$$1$$$ is the smallest possible value of $$$m$$$.

In the third test case, we can take $$$b_1 = [0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]$$$ and $$$b_2 = [0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2]$$$. It's easy to see, that $$$a_i = b_{1, i} + b_{2, i}$$$ for all $$$i$$$ and the number of different elements in $$$b_1$$$ and in $$$b_2$$$ is equal to $$$3$$$ (so it is at most $$$3$$$). It can be proven that $$$2$$$ is the smallest possible value of $$$m$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/19/2021 01:49:18 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|