The Grand Guild of Arcanum is preparing for a massive expedition into the Void. The Guild Master, Bao, has a list of adventurers categorized into n distinct character classes (such as Paladins, Mages, Rogues, Bards, etc.). The guild registry shows that there are currently ~a_i~​ adventurers available for the ~i~-th class.

To ensure the survival of the expedition teams, the Guild Council has mandated strict formation rules. Every expedition squad must consist of exactly ~k~ adventurers. However, due to clashing magical auras and incompatible fighting styles, a squad cannot contain more than one adventurer of the same class. Furthermore, each adventurer can be assigned to at most one squad.

Bao wants to deploy as many squads as possible to maximize the Guild's presence in the Void. Given the current roster of adventurers and their classes, your task is to calculate the maximum number of full, valid squads Bao can form.

Input

The first line contains a positive integer ~T~ (~1 \le T \le 1000~) — the number of test cases.

The first line of each test case contains two positive integers ~n~ and ~k~ (~1 \le k \le n \le 2 \cdot 10^5~) — the number of character classes and the required size of a squad.

The second line of each test case contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~) — the number of available adventurers of each class.

The total ~n~ across all test cases does not exceed ~2 \cdot 10^5~.

Output

For each test case, print the maximum number of squads that can be formed on a new line.

Sample Input 1

2
4 3
3 2 1 1
4 4
3 2 2 1

Sample Output 1

2
1

Notes

In the first testcase, there can be maximum ~2~ squads. The first squad will have members of class ~1~-th, ~2~-th and ~3~-rd while the second class will have members of the ~1~-st, ~2~-nd and ~4~-th class.