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

Input

Output

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.