Ling is strolling through a shopping mall when a gashapon machine catches her eye. There are $n$ types of gashapon in the machine, with $a_i$ items of the $i$-th type.

• Consuming one gashapon coin allows you to randomly obtain one gashapon.
• Consuming any $k$ gashapon allows you to exchange them with the merchant for one designated coin.
• Consuming one designated coin allows you to obtain one gashapon of a specific type from the machine.

All gashapon obtained are not put back into the machine. Ling wants to collect all $n$ types of gashapon, meaning she wants to have at least one of each type. Now, she wants to know the minimum number of gashapon coins required to guarantee that she can collect all $n$ types of gashapon.

Input

This problem contains multiple test cases. The first line contains a single positive integer $T$ ($1 \le T \le 3000$), representing the number of test cases.

For each test case: The first line contains two positive integers $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$), representing the number of gashapon types and the number of gashapon required to exchange for a designated coin, respectively. The second line contains $n$ positive integers, where the $i$-th integer is $a_i$ ($1 \le a_i \le 3000$), representing the quantity of the $i$-th type of gashapon.

It is guaranteed that the sum of $n$ over all $T$ test cases does not exceed 3000.

Output

For each test case: Output a single integer representing the minimum number of gashapon coins required to guarantee collecting all $n$ types of gashapon.

Examples

Input 1

2
2 2
1 4
4 3
8 7 6 5

Output 1

3
9