题目描述

为了保住断罪中学摇摇欲坠的“Garriton大学优质生源”地位，学生会决定组建一支“学习先锋队”，要求先锋队成员不仅自身成绩名列前茅，还要发扬自己的组织力和号召力，在无涯学海中为全校同学掌舵。
先锋队成员的遴选工作交给了学生会的二把手赵铁柱。候选人共有\(N\)名，编号为\(1 \sim N\)。赵铁柱组织学生会成员们对所有候选人进行了一系列面试，面试结果表明，这\(N\)个人都是做组织工作的好手，但每个人的行事风格差异巨大：有人推崇儒家式的“礼乐治校”，力图在校内形成互帮互助、和谐友爱的校园文化，并通过多样的文体活动来促进和谐氛围的形成；但另一些人推崇法家式的“严刑峻法”，强调校规校纪的绝对权威，通过体罚、公开检讨等方式对散漫怠惰的学生形成强有力的震慑。第\(i\)个候选人主张的“激进程度”可以用一个整数\(x_i\)（可能为负数）表示。不难想象，如果两人的激进程度差异很小，那么他们合作起来就非常愉悦，在他们管辖的范围内就能形成“\(1+1>2\)”的合作效果。
赵铁柱早已对学生会的一把手李狗蛋怀恨有加，曾经二人争夺一把手交椅的黑历史让他至今无法释怀。他看中了这个将仇人一举击垮的机会，于是他打算在先锋队人选上做手脚，让整个队伍彻底成为一盘散沙，然后暗搓搓地将之后混乱的局面归咎于李狗蛋。他打算从\(N\)个人选中挑出\(K\)个人，对于每一种选法，设选出的\(K\)个人的编号为\(p_1, p_2 \cdots p_K\)，定义“最小激进程度差”
\(D = \min \limits_{1 \le i < j \le K} \vert x_{p_i} - x_{p_j} \rvert\)
他想让\(D\)越大越好。请你求出在所有的选法中，\(D\)的最大值是多少？

输入格式

输入第一行是一个正整数\(T\)，表示测试数据的组数。之后每组数据：
第一行是两个正整数\(N, K\)；
第二行是\(N\)个整数\(x_1, x_2 \cdots x_N\)，两个数之间用一个空格隔开。

输出格式

每组数据输出一行，表示该组数据中，“最小激进程度差”\(D\)的最大值。

样例

输入

3
5 2
1 2 8 4 9
5 3
1 2 8 4 9
5 4
1 2 8 4 9

输出

8
3
1

样例说明

第一组数据中，最优选法是选择编号为\(1,5\)的人，\(x_1 = 1, \quad x_5 = 9, \quad D = 8\)；
第二组数据中，最优选法之一是选择编号为\(1,3,4\)的人，\(x_1 = 1, \quad x_3 = 8,\quad x_4 = 4,\quad D = 3\)；选择编号为\(1,4,5\)的人也可以得到最优解。

数据规模及约定

所有数据均满足：\(T \le 10, \quad 2 \le K \le N \le 10^5, \quad \lvert{x_i}\rvert \le 10^9\)
前20%数据满足：\(N \le 20\)
另外20%数据满足：\(N \le 2000, \quad K \in \{2, 3, 4\}\)
另外20%数据满足：\(N \le 2000\)
时间限制1s，空间限制64MB。