Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $t$~--- количество наборов входных данных ($1 \le t \le 10^4$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $n$ и $k$~--- количество слитков золота в хранилище и количество разрезов, которое Всадники успеют сделать ($1 \le n \le 2 \cdot 10^5; 1 \le k \le 10^9$).

Вторая строка каждого набора входных данных содержит $n$ целых чисел $a_i$, где $i$-е число описывает величину массы $i$-го слитка из хранилища ($1 \le a_i \le 10^9$).

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $2 \cdot 10^5$.