Practice on Toph

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

Who Ate the Pizza Slices?

By sakibalamin · Limits 2s, 512 MB

Misty’s life is very dramatic. No matter how careful she is, some interesting and sometimes unfortunate things happen to her all the time.

One day she made N pizzas for N of her friends. Each pizza had K slices each and was identical. Then she went to attend a contest. When she came home, she noticed that some of her pizza slices are gone! But she was supposed to give treats to her friends. But she cannot give them pizzas with missing slices. So, she came up with an idea.

As she is a perfectionist, all of her pizza slices are exactly the same. So she decided to use the remaining slices to construct new pizzas with no missing slices. But she doesn't know at least how many new pizzas she has to make again in order to give treats to all of her N friends with a full pizza with no missing slices. Please help her. Otherwise, she won’t give you treats ever again!

Input

First-line contains a single integer T (1 ≤ T ≤ 1000), number of test cases. Each test case starts with a single line containing two integers N and K (1 ≤ N, K ≤ 1000), the number of pizzas Misty has made, and the total number of slices in each pizza. Then N lines follow, containing the remaining slices ai (0 ≤ ai ≤ K) in the i'th pizza (1 ≤ i ≤ N).

Output

For each test case, output a single line which denotes the number of pizzas Misty has to make again in order to give treats to each of her N friends with a full pizza with no missing slices.

Sample

InputOutput
2
5 6
4
5
3
0
6
7 5
1
2
3
4
5
0
2
2
4

In the first case, if Misty makes two more pizzas, she will be able to give treats to all of her friends with a full pizza each, with no missing slices in them.

Similiarly, in the second case, making 4 new pizzas is enough.


Discussion

Statistics


95% Solution Ratio

FairoozREarliest, Jun '20

prodip_bsmrstuFastest, 0.0s

FairoozRLightest, 131 kB

bokaifShortest, 101B

Submit

Login to submit

Editorial

First, calculate how many slices are needed more. After that, it's simple calculation.

Toph uses cookies. By continuing you agree to our Cookie Policy.