#2322. Getting Rid of the Holidays

Getting Rid of the Holidays

Description

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

Format

Input

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

Output

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

Samples

1
5 2
6 13 10 15 7
2