该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

在我们活着的不算长久的年岁里，总能听到人们说，日子凑活凑活也就过了。很多事可以将就，但是爱情不能将就。有多少人因为害怕孤单寂寞而将就，有多少人因为父母催促而将就，又有多少人为了凑合而将就，因为将就而凑合着。就像一个死循环。生活已经在将就了，索性把爱情也将就了，还剩下什么，哪怕为自己走个心都没有。在听到“即使疲惫，也不将就；即使折磨，也要一起走到白首”的时候，很是感触。很喜欢的一句话送给你们共勉“生命如果不能浪费在我所喜欢的人身上，那我宁愿把生命浪费在自己身上”余生很长，不将就！

题目描述

给定一个包含 $n$ 个正整数的数组 $a$。每次操作，你可以选择一对 $(i, j)$，满足 $1\leq i < j\leq |a|$，并将 $|a_i - a_j|$ 添加到数组 $a$ 的末尾（即 $n$ 增加 $1$，并令 $a_n = |a_i - a_j|$）。你的任务是经过 $k$ 次操作后，最小化并输出数组 $a$ 的最小值。

输入格式

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2\le n\le 2\cdot 10^3$，$1\le k\le 10^9$），分别表示数组的长度和你需要进行的操作次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i\le 10^{18}$），表示数组 $a$ 的元素。

保证所有测试用例中 $n^2$ 的和不超过 $4\cdot 10^6$。

输出格式

对于每个测试用例，输出一个整数，表示经过 $k$ 次操作后，数组 $a$ 的最小可能值。

输入输出样例 #1

输入 #1

4
5 2
3 9 7 15 1
4 3
7 4 15 12
6 2
42 47 50 54 62 79
2 1
500000000000000000 1000000000000000000

输出 #1

1
0
3
500000000000000000

说明/提示

在第一个测试用例中，经过任意 $k=2$ 次操作后，$a$ 的最小值都将为 $1$。

在第二个测试用例中，一种最优策略是先选择 $i=1, j=2$，将 $|a_1 - a_2| = 3$ 添加到 $a$ 的末尾，此时 $a=[7, 4, 15, 12, 3]$。然后选择 $i=3, j=4$，将 $|a_3 - a_4| = 3$ 添加到 $a$ 的末尾，此时 $a=[7, 4, 15, 12, 3, 3]$。最后一次操作选择 $i=5, j=6$，将 $|a_5 - a_6| = 0$ 添加到 $a$ 的末尾。此时 $a$ 的最小值为 $0$。

在第三个测试用例中，一种最优策略是先选择 $i=2, j=3$，将 $|a_2 - a_3| = 3$ 添加到 $a$ 的末尾。无论第二次操作如何，$a$ 的最小值都不会小于 $3$。