Packing Files onto Discs

Adam is an organized man, and he has always thought carefully about how to arrange his belongings. He remembers with pleasure the hours of his youth spent moving files from his computer onto compact discs.

Two rules governed that work. First, so that every disc could be labeled clearly, he never placed more than two files on one disc. Second, he never split a single file across several discs. His discs were always large enough to make both rules possible.

Looking back, Adam wonders whether he arranged the files in the best way or wasted a few discs. You are given the capacity of the discs he used (all of his discs had the same capacity) and the list of file sizes he stored. Determine the minimum number of discs needed to store all of the files while obeying both rules.

The first line contains the number of test cases $T$. $T$ test cases follow.

The first line of each test case contains the number of files to be stored $N$ and the capacity of one disc $X$ (in MB), separated by a single space. The next line contains the sizes $S_i$ (in MB) of the $N$ files, separated by single spaces.

Limits

• $1 \le T \le 100$
• $1 \le X \le 700$
• $1 \le S_i \le X$
• $1 \le N \le 10$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of discs needed to store the given files.