Лин прогуливается по торговому центру, и её внимание привлекает автомат с капсулами-игрушками (гача-автомат). В автомате есть $n$ видов игрушек, причём игрушек $i$-го вида имеется $a_i$ штук.

• Потратив одну монету, можно случайным образом получить одну игрушку.
• Потратив любые $k$ игрушек, можно обменять их у продавца на одну «специальную монету».
• Потратив одну специальную монету, можно получить одну игрушку выбранного вида из автомата.

Все полученные игрушки не возвращаются обратно в автомат. Лин хочет собрать все $n$ видов игрушек, то есть в конечном итоге иметь хотя бы по одной игрушке каждого вида. Теперь она хочет узнать, какое минимальное количество монет ей нужно потратить, чтобы гарантированно собрать все $n$ видов игрушек.

Входные данные

В задаче несколько наборов входных данных. В первой строке содержится целое число $T$ ($1 \le T \le 3000$), количество наборов данных. Для каждого набора данных: В первой строке содержатся два целых числа $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$), обозначающие количество видов игрушек и количество игрушек, необходимое для обмена на одну специальную монету. Во второй строке содержатся $n$ целых чисел, где $i$-е число $a_i$ ($1 \le a_i \le 3000$) обозначает количество игрушек $i$-го вида. Гарантируется, что сумма $n$ по всем $T$ наборам данных не превышает $3000$.

Выходные данные

Для каждого набора данных: Выведите одну строку с целым числом, обозначающим минимальное количество монет, необходимое для гарантированного сбора всех $n$ видов игрушек.

Примеры

Входные данные 1

2
2 2
1 4
4 3
8 7 6 5

Выходные данные 1

3
9