Limits 2s, 512 MB

Little Dwayne Johnson is hosting a programming contest. A lot of teams mail him everyday to ask about various things. Little Dwayne uses Kmail to send reply mails. But Kmail only allows sending KK mails per day. If some teams don't get any reply they become dissatisfied.

Little Dwayne forgets everything after each day. So if a team mailed him on ii-th day, he will not reply them after ii-th day. Now little Dwayne wonders what is the total number of dissatisfied teams. Help him or he'll start to cry.

Input

First line contains the number of test cases TT (1T1001 ≤ T ≤ 100). Each test case starts with two integers DD and KK (1D1001 ≤ D ≤ 100, 0K1000 ≤ K ≤ 100), where DD is the number of days to consider and KK is the maximum number of mails little Dwayne can send per day. Next line contains DD integers where ii-th integer, aia_i (0ai1000 ≤ a_i ≤ 100) denotes the number of mails little Dwayne received on ii-th day.

Output

For each test case print the number of dissatisfied teams.

Sample

InputOutput
1
3 10
12 5 14
6

In the sample, little Dwayne can send reply to at most 10 teams on first day. So 2 teams are dissatisfied. On second day no teams are dissatisfied. On third day 4 teams are dissatisfied. So total 6 teams are dissatisfied.

Submit

Login to submit.

Statistics

95% Solution Ratio
aaman007Earliest, May '18
Rafi9998Fastest, 0.0s
Big_PappaLightest, 0 B
ShuddhoShortest, 105B
Toph uses cookies. By continuing you agree to our Cookie Policy.