Selection
Time limit: 30sec. Submitted: 102 
Source : SCU Programming Contest 2005 Final

Given a sequence of integers A1A2...AN, you can divide it into at most M consecutive parts, then select some integers from each part respectively if the sum of the selected integers in that part is not more than a given number MaxV. How many numbers can you select at most in total? This is the task for you. 

Input

The first line of the input will give the number of test cases. The first line of each test case consists of three numbers N, M and MaxV (1<=N<=1500, 1<=M<=50, 1<=MaxV<=10000), N is the length of the number sequence, M and MaxV is defined in the problem above, then follows N lines, each representing an integer Ai (1<=Ai<=10000). 

Output

For each test case, print only one integer, the number you can select at most in a single line. 

Sample Input 

1
8 2 50
2
25
25
9
6
4
10
5
Sample Output 
7