Limits 1s, 512 MB

BDesh is a very peaceful country with a smaller population. Recently a Spider Demon with a dangerous kind of venom found in BDesh. Spider Demon pushed his venom into people’s veins and the people became spider-people. I know you are scared.

But don’t worry, BDesh has a very talented and furious health minister named Zenitsu Agatsuma. He has some psychic power, and using these powers Zenitsu somehow manages to kill the Spider Demon.

Ahh! people are relaxed now and cheering Zenitsu. But the people who already are a spider-people still haven't recovered. To change these spiders into people, Zenitsu tries psychic power again but fails. After a long time, Zenitsu’s friend named Shinobu Kochu came with the glorious news that she invented a vaccine to recover these people. Now it’s time to start the vaccination. The process lasted for NN days.

After starting the vaccination process it is observed that on i-th day if aia_ispider-people come to take vaccine they can only vaccinate XiX_i number of spider-people and get them fully recovered on that day where XiX_i is the largest multiple of KK which less or equal to aia_i and the remaining become spider-people forever.

You’re given NN integers where aia_i is the number of spider-people who came to take the vaccine on i-th day. Your task is to determine how many people become spider-people forever from not getting vaccinated if they vaccinate as many people as possible.

Input

The first line will be a single integer TT indicating the number of test cases.  Each of the test cases will contain two integers NN and KK. Then the next line will contain NNintegers a1,a2,a3,,ana_1, a_2, a_3,…,a_n the number of vaccinated people each day.

1T101 \leq T \leq 10

1N,K1001 \leq N, K \leq 100

1a1,a2,a3,,an10001 \leq a_1, a_2, a_3,…,a_n\leq 1000

Output

You have to output TT lines in the format “Case X: Y”(without quotes) where XX is the number of test case and YY is the total number of people who will become permanently spider-people.

Sample

InputOutput
2
5 4
5 100 1 12 15
3 1
13 22 1
Case 1: 5
Case 2: 0

In the first case, on the first day, the maximum people who can get vaccine is 44. On the second day, everyone can get vaccine as 100100 itself is a multiple 44. On the third day, no one can get vaccine as the largest multiple of 44 less than or equal to 11 is 00. On the fourth day, everyone can get vaccine as 1212 itself is a multiple of 44. Finally, on the fifth day, only 1212 people can get vaccine as it is the largest multiple of 44 less than or equal to 1515.


Submit

Login to submit.

Statistics

98% Solution Ratio
MursaleenEarliest, Apr '21
the.shoaib2Fastest, 0.0s
MursaleenLightest, 131 kB
Jitendra_BaruaShortest, 142B
Toph uses cookies. By continuing you agree to our Cookie Policy.