Ling przechadza się po centrum handlowym, gdy jej uwagę przykuwa automat z zabawkami typu gacha. W automacie znajduje się łącznie $n$ rodzajów zabawek, przy czym zabawek $i$-tego rodzaju jest $a_i$.

• Zużycie jednej monety pozwala losowo otrzymać jedną zabawkę.
• Zużycie dowolnych $k$ zabawek pozwala wymienić je u sprzedawcy na jedną monetę specjalną.
• Zużycie jednej monety specjalnej pozwala otrzymać jedną zabawkę wybranego rodzaju z automatu.

Wszystkie zabawki, które wypadły z automatu, nie są do niego zwracane. Ling chce zebrać wszystkie $n$ rodzajów zabawek, co oznacza, że na końcu chce posiadać co najmniej jedną zabawkę każdego rodzaju. Chce wiedzieć, ile co najmniej monet musi zużyć, aby mieć pewność, że uda jej się zebrać wszystkie $n$ rodzajów zabawek.

Wejście

Zadanie zawiera wiele zestawów danych. Pierwsza linia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 3000$), oznaczającą liczbę zestawów danych.

Dla każdego zestawu danych: Pierwsza linia zawiera dwie liczby całkowite $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$), oznaczające odpowiednio liczbę rodzajów zabawek oraz liczbę zabawek potrzebną do wymiany na monetę specjalną. Druga linia zawiera $n$ liczb całkowitych, gdzie $i$-ta liczba to $a_i$ ($1 \le a_i \le 3000$), oznaczająca liczbę zabawek $i$-tego rodzaju.

Suma $n$ we wszystkich zestawach danych nie przekracza $3000$.

Wyjście

Dla każdego zestawu danych: Wypisz w jednej linii jedną liczbę całkowitą, oznaczającą minimalną liczbę monet potrzebną do zagwarantowania zebrania wszystkich $n$ rodzajów zabawek.

Przykład

Wejście 1

2
2 2
1 4
4 3
8 7 6 5

Wyjście 1

3
9