A factory has N Product Quality Analysts (PQA) working in a single line. The first PQA is standing at the start of the product line and the Nth PQA is standing at the end of the product line. The first PQA starts the checking of a product and takes t1 minutes and then hands it over to the 2nd PQA. More formally, the ith PQA takes ti minutes time to check a product and then hand it over to the (i+1)th PQA. When the Nth PQA completes his inspection for a product, we call the product a Verified Product.
For example, Let there be 4 PQAs working in the factory and they take 2, 3, 1, and 4 minutes time respectively to check a product. Product checking timeline these PQA is as follows:
| Product | By PQA1 | By PQA2 | By PQA3 | By PQA4 | ||
| 1st Product | Start of checking | 1 | 3 | 6 | 7 | |
| End of checking | 2 | 5 | 6 | 10 | ||
| 2nd Product | Start of checking | 3 | 6 | 9 | 11 | |
| End of checking | 4 | 8 | 9 | 14 | ||
So, the first product will be verified at the end of the 10th minute, and the second product will be verified at the end of the 14th minute.
The manager of the company wants to arrange these N product quality analysts in such a way that minimizes the production time for the first K verified products. You have to calculate how many ways he can do so.
Input
Input starts with an integer T (1 ≤ T ≤ 1001) denoting the number of test cases.
Each of the test cases starts with two integers N (1 ≤ N ≤ 20) and K (1 ≤ K ≤ 1010). The next line of the test case will contain N space-separated integers t1, t2, ... tn (1 ≤ ti ≤ 108).
Output
The output should be in the format Case X: Y where X is the case number and Y is the number of ways. Please see the output in the sample case for more clarity.
Sample
| Sample Input | Sample Output |
|---|---|
2 1 1 5 2 10 2 2 | Case 1: 1 Case 2: 2 |