Description

B国的国王Johnny在他在位的短短几年里制定了不少的节日（事实上没超过30个），这些节日是为了尊敬各种各样他所想到的东西而设立的。每过一段固定的时间，一个节日将会被举行（即节日都是周期性的，每个节日的周期可能会不同），并且过节的那一天会普天同庆，将有盛会演奏、歌舞表演。有时候几个节日会在一天同时发生，并且有可能所有节日在同一天发生。如果出现这种情况，节日将被联合庆祝并且举行更大宴会。某一天所有节日都发生了。可能由于玩得太high了，在宴会后，国王Johnny表现开始有点古怪而且他需要与世隔绝几天。
在国王Johnny不在的时候（约48小时）你被指定处理B国的政事。最为一个真正的爱国者，你知道这些节日是对人民没有好处的，并且你想在国王Johnny回来之前（Johnny将不会介意，因为他在宴会后会忘记所有事情）删去一些节日。然而悲哀的是，这里的人民不知道什么对他们有好处，什么对他们有坏处，如果你删去了超过k个节日他们将会反抗。你的任务是删除不超过k个节日使得最小的两次有节日的日子之间的间隔最大。

Input

文件的第一行有一个单独的整数T<=200,表示测试数据的组数。接下来有T组测试数据。对于每个测试数据，第一行包含两个整数n和K
(1 < = K < n < = 30 )，表示节日的总数和最多可以删除的节日数。接下来的一行包含n个整数表示每个节日的周期，第i个整数表示编号为i的整数的周期，每个节日的周期将不会超过10^18。

Output

对于每个测试数据，输出一行一个数，表示最大的间隔.

Sample Input

Sample Output

Hint

Source