A tree is a connected graph without cycles. The distance between two nodes is the number of edges on the shortest path between them. The degree of a node is the number of edges connected to the node. The size of a tree is the number of nodes in it.

Your friend gave you a challenge; he tells you he has drawn one tree which you cannot see but he will give you some hints about it. First he picks a random node as the source of the tree. Then he picks $n$ different nodes from the tree, and he tells you the distance of each one of them to the source. As an added hint, he also tells you that no node in the tree has a degree larger than $k$.

Your challenge is to figure out what is the minimum possible size of the tree based on the hints you were given, or determine that such a tree does not exist.

The first line of input contains a single integer $T$ ($1 \le T \le 10^5$), the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \leq n,k \leq 10^5$), the number of picked nodes and the degree limit, respectively.

The second line contains $n$ integers $d_1, d_2, \dots, d_n$ ($0 \leq d_i \leq 10^9$), the distances of the picked nodes.

It is guaranteed that there's at most one node with distance zero.

The total sum of $n$ over all test cases doesn't exceed $10^6$.

For each test case, on a single line, if it is impossible to have such a tree, print -1. Otherwise, print the minimum possible size of the tree.