600. K for the Price of One

0

Hard

Input Format

The first line contains an integer t, which represents the number of test cases. The following lines provide a description of t test cases. Each test case begins with a line containing three integers n, p, and k. These represent the number of goods in the store, the number of coins Vasya has, and the number of goods that can be purchased for the price of the most expensive item, respectively. The second line of each test case contains n integers ai, which represent the prices of the goods. It is guaranteed that the sum of n for all test cases does not exceed 2⋅105.

Output Format

For each test case, print a single integer m on a separate line. This represents the maximum number of goods that Vasya can purchase.

Example

Input

8 5 6 2 2 4 3 5 7 5 11 2 2 4 3 5 7 3 2 3 4 2 6 5 2 3 10 1 3 9 2 2 10000 2 10000 10000 2 9999 2 10000 10000 4 6 4 3 2 3 2 5 5 3 1 2 2 1 2

Output

3 4 1 1 2 0 4 5

Constraints

1≤t≤104
1≤ai≤104
2≤n≤2⋅105
1≤p≤2⋅109
2≤k≤n

View Submissions

Console