Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Vaccination in BDesh

By Wl.Reino · 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.


    Discussion

    Statistics


    100% Solution Ratio

    MursaleenEarliest, 1w ago

    def_UserNameFastest, 0.0s

    MursaleenLightest, 131 kB

    One_AutumnLeafShortest, 191B

    Submit

    Login to submit

    Editorial

    To solve the problem we need knowledge about how Loop works and some basic arithmetic operations. We...