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 $N$ days.

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

You’re given $N$ integers where $a_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 $T$ indicating the number of test cases.  Each of the test cases will contain two integers $N$ and $K$. Then the next line will contain $N$integers $a_1, a_2, a_3,…,a_n$ the number of vaccinated people each day.

$1 \leq T \leq 10$

$1 \leq N, K \leq 100$

$1 \leq a_1, a_2, a_3,…,a_n\leq 1000$

Output

You have to output $T$ lines in the format “Case X: Y”(without quotes) where $X$ is the number of test case and $Y$ 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 $4$. On the second day, everyone can get vaccine as $100$ itself is a multiple $4$. On the third day, no one can get vaccine as the largest multiple of $4$ less than or equal to $1$ is $0$. On the fourth day, everyone can get vaccine as $12$ itself is a multiple of $4$. Finally, on the fifth day, only $12$ people can get vaccine as it is the largest multiple of $4$ less than or equal to $15$.

Statistics

100% Solution Ratio

MursaleenEarliest, 1w ago

MursaleenLightest, 131 kB

One_AutumnLeafShortest, 191B