This 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$.


-----Input-----

The 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$.


-----Output-----

For each test case, print a single integer — the minimum possible cost of an array $p$ satisfying the condition above.


-----Examples-----

Input
7
5 2
4 5 6 8 11
5 12
4 5 6 8 11
3 1
2 9 15
7 3
2 3 5 5 6 9 10
6 56
54 286 527 1436 2450 2681
3 95
16 340 2241
2 2
1 3
Output
2
0
13
1
4
7
0


-----Note-----

In 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]$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Sorting

Greedy algorithms

Complete search

Number theory
Skill types: Complete search

Sorting

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	a = [*map(int, input().split())]
	ps = [0] * (10 ** 5 + 10)
	for i in range(N):
		(pv, j) = (10 ** 9, 1)
		while j <= min(a[i], K):
			nv = a[i] // j
			ps[nv + 1] = max(ps[nv + 1], pv)
			pv = nv
			j = a[i] // (a[i] // j) + 1
		ps[0] = max(ps[0], pv)
	(ans, cm) = (10 ** 9, 0)
	for i in range(a[0] + 1):
		cm = max(cm, ps[i])
		ans = min(ans, cm - i)
	print(ans)


def compute(a, p):
	s = [a[i] // p[i] for i in range(len(a))]
	return max(s) - min(s)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = max(a)
	l = min(a)
	t = m // k
	if k >= m:
		print(0)
	elif k == 1:
		print(max(a) - min(a))
	else:
		t = m // k
		temp = 3000
		for l in range(t + 1, 2 * t + 2):
			p = [a[i] // l + 1 for i in range(n)]
			ss = compute(a, p)
			temp = min(temp, ss)
			if temp == 0:
				break
		print(temp)


for _ in range(int(input())):
	(_, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(min((max((x // min(k, x // u) for x in a)) - u for u in range(1, a[0] + 1))))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	opt = math.inf
	for low in range(1, a[0] + 1):
		high = max((x // min(k, x // low) for x in a))
		opt = min(opt, high - low)
	print(opt)


def main():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = float('inf')
	mx = max(arr)
	for d in range(1, mx + 1):
		aux = []
		for z in arr:
			if z <= d:
				aux.append(z)
			else:
				a = min(z // d, k)
				aux.append(z // a)
		poss = max(aux) - min(aux)
		ans = min(poss, ans)
	return ans
for _ in range(int(input())):
	print(main())


import bisect
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	c = [sorted(set((x // p for p in range(1, k + 1)))) for x in a]
	u = min((x[0] for x in c))
	v = min((x[-1] for x in c))
	opt = math.inf
	for low in range(u, v + 1):
		if low == 0:
			high = a[-1] // k
		else:
			high = max((x // min(k, x // low) for x in a))
		opt = min(opt, high - low)
	print(opt)