Fresh Chocolate (Small)

You are the public relations manager for a chocolate manufacturer. The company's image has suffered because customers think the owner is cheap and miserly. You hope to undo that impression by offering a free factory tour and chocolate tasting.

Soon after starting the project you found that the owner's reputation is deserved. He agreed to give away free chocolate only if you keep the cost as low as possible. The chocolate comes in packs of $P$ pieces. You would like to open new packs for each tour group, but the owner insists that leftover pieces from one group must be used on the next group before any new pack is opened.

Suppose each pack contains $P = 3$ pieces and a group of 5 people arrives. You open two packs to give one piece to each person, and one piece is left over. Suppose a group of 6 people comes next. They receive the leftover piece, then you open two more packs to finish serving them, so one piece is left over again. If two groups of 4 people each come right after, the first of them gets the leftover piece plus a full pack, and the last group of 4 gets its pieces from two newly opened packs. You cannot open a new pack until all leftovers are used up, even if you plan to use the whole new pack immediately.

In that example 2 of the 4 groups (the first and the last) got all of their chocolate from freshly opened packs. The other 2 groups got some fresh chocolate and some leftovers. Handing out leftovers is a poor way to undo the owner's miserly image, but you had to accept this system to get the project approved.

You have requests from $N$ groups, and each group has stated how many people will come. Groups enter one at a time. You want an order that maximizes the number of groups that get only fresh chocolate and no leftovers. You cannot reject a group, no group takes chocolate twice, and every person in every group must get exactly one piece.

In the example above, if the order were 4, 5, 6, 4 instead of 5, 6, 4, 4, then 3 groups (all but the group of 5) would get only fresh chocolate. For that set of groups no arrangement serves all four groups only fresh chocolate, so 3 is the best possible.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of two lines. The first line contains two integers $N$, the number of groups coming for a tour, and $P$, the number of pieces of chocolate per pack. The second line contains $N$ integers $G_1$, $G_2$, ..., $G_N$, the number of people in each group.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le G_i \le 100$ for all $i$
• $2 \le P \le 3$

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of groups that receive only fresh chocolate under an order that maximizes that number.

The first sample test case is the one explained in the statement. Besides the order given above, other orders such as 6, 5, 4, 4 also maximize the number of groups that get only fresh chocolate, although the groups that get it are not the same. Only the number of groups with the best experience is counted, not the total number of people in them.

In the second sample test case the groups are the same as in the first one, but each pack contains two pieces. Several orders, for instance 4, 4, 6, 5, then make every group get only fresh chocolate.

In the third sample test case every group is a single person and all of them eat from the same pack. Only the first group to enter gets a freshly opened pack.