Server Time: Wed Sep 18, 2019 9:26 am
Welcome ( logout
1127 - Funny Knapsack
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 32 MB

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 Input

Output for Sample Input

3

1 1

1

1 1

2

3 10

1 2 4

Case 1: 2

Case 2: 1

Case 3: 8

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan