Robert Langdon's new book is out, titled "Religious Iconology". The book talks about hidden meanings in various symbols used in religious literature and artwork, how some religions have a human form of representation like Christianity while other use textual representation, like Islam.

Famed by the book, he gets book signing requests from different countries. He is visiting Poland this time. Signings will take place at various venues in the country, and many people are expected to attend.

Being anticipatory in nature, he wonders how many pen refills he must carry so as to not run out of ink during the signings. Can you please help him calculate this? The full refill in the pen is also counted.

Input

First line contains T, the number of test cases.

Each test case begins with integers N and K, number of signings and number of signatures he can do with one refill (Each refill has equal capacity, does same number of signatures).

Next line of each test case has N space separated integers, ith number of this line telling number of people that are attending the ith signing.

Output

For each test case, output one line telling the minimum number of refills that he must carry.

Constraints

1 <= T <= 100

1 <= N <= 1000

1 <= K <= 1000

Attendance at each signing is between 1 and 1000

Example

Input:
2
3 5
4 11 15
5 4
1 1 1 1 1

Output:
6
2

Explanation

For the first case: each refill can do 5 signs. First one will do 4 signs at the first signing, and 1 for the second one. The he will need 2 more at the second signing. At the end, he will need 3 for the last signing. So in total, he needs 6 refills.