【问题描述】

众所周知，一年中有许许多多各种各样的节日，令人兴奋的是，大多数节日都有假期。

然而，小D生活在一个神奇的国度Z国。Z国有n个不同的节日，每个节日有其独特的周期，他们的国庆日就是所有节日重合的日子。你可以认为每个节日过节那天都会放一天假^_^。 由于小D是一个勤奋努力的好学生，他对Z国众多的节日和假期表示不满，于是神奇的小D会在这n个不同的节日里选出K个节日呆在学校好好学习（神奇的小D和自己有个神奇的约定，如果某一天有多个节日，只要其中存在一个节日小D不想呆在学校里好好学习，他就会出去玩）。神奇的小D希望他相邻的出去玩的日子的间隔的最小值最大。当然，忙碌的小D怎么会有时间研究有关放假的问题，那么这个神奇而艰巨的任务就交给你了。

由于小D从来不关心节日放假情况，现在他从不同的途径得到了不同的节日放假情况，对于每一种情况你都要告诉小D，你都要帮他找到哪些节日他应该呆在学校好好学习，使得他相邻的出去玩的日子间隔的最小值最大。并告诉他这个最大的间隔。

【输入格式】

第一行输入一个正整数T表示数据组数。

接下来有T组数据。

对于每一组数据，第一行输入两个正整数n，k，表示Z国的节日个数和小D要呆在学校好好学习的节日个数。

接下来一行n个正整数，第i个正整数ti 表示第i个节日的周期（从国庆日开始，每ti天就是节日i）。

【输出格式】

对于每组数据输出一行表示该组数据的答案。

【样例】

输入数据 1

2
5 2
6 13 10 15 7
4 1
3 4 12 8

输出数据 1

2
4

【数据说明】

对于40%的数据，保证1≤k<n≤15

对于70%的数据，保证1≤k<n≤30

对于100%的数据，保证T≤10，1≤k<n≤45，ti≤10^18