Problem F: zser vs lx

Problem F: zser vs lx

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 86  Solved: 12
[Submit] [Status] [Web Board] [Creator:]

Description

lx学长和zser学长正在玩这样一个游戏,每局游戏的开始的时候,lx手持一瓶可以认为是无穷无尽的饮料,而zser学长手中仅仅有一个空杯子。

 在这个游戏中,分为n轮,在每一轮的游戏中,lx学长向zser学长中的杯子倒入h个单位的饮料(注意:每一轮的倒入的饮料单位数量在游戏开局以前就已经决定好了,并且不会改变)接着zser学长会跑出一个均匀并且有k个面的筛子,来得到一个1到k之间的数d,如果当前杯中的饮料h小于等于d,那么lx学长会记一分,并且zser学长会将杯中的饮料一饮而尽,反之,zser学长会记一分,并且lx学长会喝掉杯中d个单位的饮料。

在游戏n轮之后,得分高的人就会获胜。如果现在zser学长可以预测在游戏每一轮中,自己掷骰子所扔的点数,那么使得zser学长获胜的h,最少是多少,即每次倒入自己杯中的饮料单位数最少是多少?


Input

第一行输入一个t代表测试数据组数 (1 <= t <= 10)

接下来第一行输入n,k,代表n轮游戏和筛子有k个面 (1 <= n,k <= 100000 && n 为奇数)

接下来n个数字,代表每一轮zser学长掷骰子的点数d[i] (1 <= d[i] <= k)

Output

输出如果zser在获胜的情况下,每轮最少需要往zser杯子中倒得饮料单位数量h

Sample Input Copy

1
5 6
3 6 6 2 1

Sample Output Copy

4

HINT