Fresh Chocolate (Large)

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 new project, you realized that the owner's reputation is well deserved: he only agreed to give away free chocolate if you would minimize the cost. The chocolate comes in packs of $P$ pieces. You would like to open new packs for each tour group, but the owner insists that if there are leftover pieces from one group, they must be used on the next tour group before you open any new packs.

Suppose that each pack contains $P = 3$ pieces and that a tour group with 5 people comes. You open two packs to give one piece to each person, and one piece is left over. Suppose that another tour group with 6 people comes after that. They receive the leftover piece, then you open two more packs to finish giving them their samples, so one piece is left over again. If two groups with 4 people each come right after, the first of those gets the leftover piece plus a full pack, and the last 4 person group gets its pieces from two newly opened packs. You cannot open new packs until all leftovers have been used up, even if you plan on using all of the new pack immediately.

In the example above, 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. Giving out leftovers is not the best way to undo the owner's miserly image, but you had to accept this system to get your cheap boss to agree to the project.

You have requests from $N$ groups, and each group has specified the number of people that will come into the factory. Groups come in one at a time. You want to bring them in in an order that maximizes the number of groups that get only fresh chocolate and no leftovers. You cannot reject groups, you cannot have a group get chocolate more than once, and you need to give exactly one piece to each person in each group.

In the example above, if the order were 4, 5, 6, 4 instead of 5, 6, 4, 4, a total of 3 groups (all but the 5 person group) would get only fresh chocolate. For that set of groups it is not possible to do better, because no arrangement makes all groups get only fresh chocolate.

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, \dots, G_N$, the number of people in each of the groups.

Limits

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

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 when you bring the groups in in an order that maximizes that number.

Several orders can reach the maximum. With $P = 3$ and group sizes 4, 5, 6, 4, the order 6, 5, 4, 4 also gives 3 groups that get only fresh chocolate, although the groups that get it are not the same ones. Only the number of such groups matters, not which groups they are and not how many people are in them. With the same group sizes and $P = 2$, several orders, for instance 4, 4, 6, 5, make every group get only fresh chocolate. If every group is a single person, they all eat from the same pack, so only the first group to come in gets a freshly opened pack.