Given n integers and a knapsack of weight W, you have to count the number of combinations for which you can add the items in the knapsack without overflowing the weight.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case contains two integers n (1 ≤ n ≤ 30) and W (1 ≤ W ≤ 2 * 109) and the next line will contain n integers separated by spaces. The integers will be non negative and less than 109.
Output
For each set of input, print the case number and the number of possible combinations.
Sample
| Sample Input | Sample Output |
|---|---|
3 1 1 1 1 1 2 3 10 1 2 4 | Case 1: 2 Case 2: 1 Case 3: 8 |