切胡萝卜（困难版）

• 时间限制：5 秒
• 内存限制：64 MiB

题目描述

给定长度为 $n$ 的非降整数数组 $a_1,a_2,\ldots,a_n$ 和整数 $k$。

定义整数数组 $p_1,p_2,\ldots,p_n$ 的代价为

$$\max_{1\le i\le n}\left\lfloor\frac{a_i}{p_i}\right\rfloor- \min_{1\le i\le n}\left\lfloor\frac{a_i}{p_i}\right\rfloor.$$

请在每个 $p_i$ 都满足 $1\le p_i\le k$ 的条件下，求最小代价。

输入格式

第一行包含测试组数 $t$。

每组第一行包含 $n,k$，第二行包含 $n$ 个整数 $a_i$。

输出格式

每组输出一行一个整数，表示最小代价。

样例输入 1

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

样例输出 1

2
0
13
1
4
7
0

数据范围

• $1\le t\le100$；
• $1\le n,k\le10^5$；
• $1\le a_1\le a_2\le\cdots\le a_n\le10^5$；
• 所有测试组的 $n$ 之和不超过 $10^5$。

本题采用独立测试点计分。

子任务编号	分值	特殊限制
1	20	每组 $n,k\le7$，且 $\sum n\le50$
2	40	每组 $a_n\le3000$，且 $\sum n\le2000$
3		无特殊限制