D1. Chopping Carrots (Easy Version)time limit per test4 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard outputThis is the easy version of the problem. The only difference between the versions is the constraints on n, k, a_i, and the sum of n over all test cases. You can make hacks only if both versions of the problem are solved.Note the unusual memory limit.You are given an array of integers a_1, a_2, \ldots, a_n of length n, and an integer k.The cost of an array of integers p_1, p_2, \ldots, p_n of length n is \max\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right) - \min\limits_{1 \le i \le n}\left(\left \lfloor \frac{a_i}{p_i} \right \rfloor \right).Here, \lfloor \frac{x}{y} \rfloor denotes the integer part of the division of x by y. Find the minimum cost of an array p such that 1 \le p_i \le k for all 1 \le i \le n.InputThe first line contains a single integer t (1 \le t \le 100) — the number of test cases.The first line of each test case contains two integers n and k (1 \le n, k \le 3000).The second line contains n integers a_1, a_2, \ldots, a_n (1 \le a_1 \le a_2 \le \ldots \le a_n \le 3000).It is guaranteed that the sum of n over all test cases does not exceed 3000.OutputFor each test case, print a single integer — the minimum possible cost of an array p satisfying the condition above.ExampleInput
75 24 5 6 8 115 124 5 6 8 113 12 9 157 32 3 5 5 6 9 106 5654 286 527 1436 2450 26813 9516 340 22412 21 3Output
2
0
13
1
4
7
0
NoteIn the first test case, the optimal array is p = [1, 1, 1, 2, 2]. The resulting array of values of \lfloor \frac{a_i}{p_i} \rfloor is [4, 5, 6, 4, 5]. The cost of p is \max\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) - \min\limits_{1 \le i \le n}(\lfloor \frac{a_i}{p_i} \rfloor) = 6 - 4 = 2. We can show that there is no array (satisfying the condition from the statement) with a smaller cost.In the second test case, one of the optimal arrays is p = [12, 12, 12, 12, 12], which results in all \lfloor \frac{a_i}{p_i} \rfloor being 0.In the third test case, the only possible array is p = [1, 1, 1].
75 24 5 6 8 115 124 5 6 8 113 12 9 157 32 3 5 5 6 9 106 5654 286 527 1436 2450 26813 9516 340 22412 21 3
2 0 13 1 4 7 0 
['binary search', 'brute force', 'constructive algorithms', 'greedy', 'number theory', '*1700']