Problem C
Max Arithmetic Subsequence

You are given a strictly increasing array of $n$ numbers $0\leq a_1<a_2<\ldots <a_ n \leq 10^{18}$. Define an arithmetic progression subsequence as a series of indices $i_1<i_2<\ldots <i_ k$ such that $a_{i_2}-a_{i_1} = a_{i_3}-a_{i_2}\ldots = a_{i_ k}-a_{i_{k-1}}$.

A constant $c$ is also given. Does the maximum length arithmetic progression subsequence of array $a$ contain strictly greater than $n/ c$ elements? If yes, print the maximum length of all arithmetic progression subsequences, otherwise, print $-1$.

Input

The first line contains one integer $t$ $(1\leq t \leq 1\, 000)$ — the number of test cases. Then $t$ cases follow.

The first line of each test case contains two integers n and c $(2\leq n\leq 100\, 000, 2 \leq c \leq 5)$ — the length of the array, and the minimum ratio for the arithmetic subsequence length.

The second line of each test case contains n integers $a_1,a_2,\ldots ,a_ n$ $(0\leq a_ i\leq 10^{18})$ — the array given in the problem.

It’s guaranteed that the sum of $n$ over all test cases doesn’t exceed $100\, 000$.

Output

For each test case, output a single integer — the answer to the problem.

3
4 2
0 1 3 5
4 2
0 1 3 4
9 2
1 3 4 5 9 15 21 22 27

3
-1
5