In Abby's area the water is available in the tap only from 6AM to 8AM. So, Abby thought she would store water during that time. But to store water Abby needs some buckets, thus, she went to the bucket section in the supermarket.
There were a lot of shelves in the bucket section. There were different sizes of buckets in different shelves. Every bucket in the same shelf has the same size. Abby saw a ladder leaning on the shelves and climbed up to reach the topmost shelf. After reaching the topmost shelf, she suddenly realized she can hold only one bucket at a time on one hand because she needs to use the other hand to hold on to the ladder and climb down. Note that, she can not climb up using one hand because she is not that strong and once she climbs all the way down she can't climb up the ladder again cause a lot of people are waiting to use the ladder as well.
Abby might not be strong, but she is intelligent in deed. She thought of an idea using which she can pick as many buckets as possible in such a way that she won't have to hold more than one bucket.
Input
First line of the input there is an integer T, the number of test cases.
In each test case, there are two integers N,K, the number of shelves and the maximum total size abby can hold. In the next line there are N integers ith denotes the size of buckets on ith shelf. Note that the 1st shelf is closest to the ground and the N-th bucket is the top most one.
Output
For each testcase output a line "Case $X: Y" where X is the case number and Y is the maximum number of buckets picked by Abby.
Sample
| Input | Output |
|---|---|
2 9 14 6 4 2 5 7 5 3 4 1 5 9 4 3 5 2 1 | Case $1: 4 Case $2: 3 |
In the 1st test case, Abby can pick
Bucket of size 1 from 9th shelf, skip 8th shelf and climb down
Put the Bucket of size 1 into the Bucket of size 3 and pick it up from 7th shelf, skip the 6th,5th,4th and 3rd shelves and climb down
Put the Bucket of size 3 into the Bucket of size 4 from 2nd shelf skip, pick it up, climb down
Put the Bucket of size 4 into the Bucket of size 6 from 1st shelf
Total number of buckets is 4. Total size=1+3+4+6=14 ≤ K
In the 2nd test case, Abby can pick
Bucket of size 1 from 5th shelf and climb down
Put the Bucket of size 1 into the bucket of size 2 from 4th shelf pick it up and skip 3rd shelf climb down
Put the Bucket of size 2 into the bucket of size 3 from 2nd shelf and climb down
Total number of buckets is 3. Total size=1+2+3=6 ≤ K
