Aya está paseando por un centro comercial cuando una máquina de gashapon (máquina de cápsulas sorpresa) llama su atención. La máquina contiene $n$ tipos de cápsulas, y hay $a_i$ unidades del tipo $i$.

• Consumir una moneda de gashapon permite obtener una cápsula al azar.
• Consumir cualquier cantidad de $k$ cápsulas permite intercambiarlas con el comerciante por una moneda de selección.
• Consumir una moneda de selección permite obtener una cápsula de un tipo específico de la máquina.

Las cápsulas obtenidas no se vuelven a introducir en la máquina. Aya quiere coleccionar los $n$ tipos de cápsulas, es decir, tener al menos una de cada tipo al final. Ahora quiere saber cuántas monedas de gashapon necesita como mínimo para garantizar que podrá coleccionar los $n$ tipos de cápsulas.

Entrada

Este problema contiene múltiples casos de prueba. La primera línea contiene un número entero positivo $T$ ($1 \le T \le 3000$), que indica el número de casos de prueba. Para cada caso de prueba: La primera línea contiene dos números enteros positivos $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$), que representan el número de tipos de cápsulas y la cantidad de cápsulas necesarias para intercambiar por una moneda de selección, respectivamente. La segunda línea contiene $n$ números enteros positivos, donde el $i$-ésimo número entero es $a_i$ ($1 \le a_i \le 3000$), que representa la cantidad de cápsulas del tipo $i$. Se garantiza que la suma de $n$ en los $T$ casos de prueba no supera 3000.

Salida

Para cada caso de prueba: Imprima una línea con un número entero que represente la cantidad mínima de monedas de gashapon necesarias para garantizar la obtención de los $n$ tipos de cápsulas.

Ejemplos

Entrada 1

2
2 2
1 4
4 3
8 7 6 5

Salida 1

3
9